Was die Gesamtlaufzeit des folgenden Codes ist (N ist ein int-Variable)

Question

ich für die Prüfung vorbereite, wo ich auf diese Frage kam:

Was die Gesamtlaufzeit des folgenden Codes (N ist ein int-Variable)

Z z = new Z(N); 
for (int i = 0; i < N; i++) z.insert("Bob", i); 

Klasse Z:

public class Z 
{ 
    String[] names; 
    Integer[] numbers; 
    int N = 0; 

    public Z(int cap) 
    { 
     names = new String[cap]; 
     numbers = new Integer[cap]; 
    } 


    public Integer find(String S) 
    { 
     for (int i = 0; i < N; i++) 
     { 
      if (names[i].equals(S)) return numbers[i]; 
     } 
     return null; 
    } 

    public void insert(String S, Integer M) 
    { 
     for (int i = 0; i < N; i++) 
     { 
      if (names[i].equals(S)) numbers[i] = M; 
     } 
     names[N] = S; 
     numbers[N] = M; 
     N++; 
    } 
} 

ich denke, die Antwort auf diese Frage O (n^2). Die ersten für die Schleife dauert O (n) mal, und das Verfahren Einsatz nimmt O (n) mal (Anmerkung: n ++ auf jedem Einsatz call), die O insgesamt ergibt (n^2)

Answer 1

Zuerst beachte, dass die N Variable im Hauptteil ist nicht das gleiche wie die N verwiesen innerhalb der Objektinstanz.

Nachdem das z Objekt erstellt wird, sein privates N Mitglied ist gleich 0 und erhöht nur bei jedem Aufruf zu insert.

Die Anzahl der Wiederholungen der Schleife in der insert-Methode ist gleich der Anzahl der vorherigen Aufrufe an die insert-Methode.

so dass die Gesamtzahl aus Iterationen im insert Verfahren (wobei alle N zusammen nennt) ist:

  _{Σ i = 1-0..N} (i)

Diese

ist gleich:

  ½N (N-1)

die ½N² ist - ½N und damit O (n²)