Laufzeit und Platz Komplexität dieses Codes

Question

Ich habe ein wenig Mühe bei der Bestimmung der großen o dieser Lösung Ich kam auf eine CTCI Frage Die Raumkomplexität sollte O (1) sein, ist aber die Laufzeit AUF)? Es scheint mehr nach O (N^2) wegen der while-Schleife zu sein. Die while-Schleife wird jedoch nicht für jedes Element innerhalb der for-Schleife N-mal ausgeführt.

public static int[] missing_two(int [] n){ 

     for(int i=0;i<n.length;i++){ 
      while(n[i]!=i){ 
       int temp=n[i]; 
       n[i]=n[n[i]]; 
       n[temp]=temp; 
      } 
     } 

    } 

Wäre 6,0,1,2,3,4,5 ein Beispiel für den schlimmsten Fall hier? Die while-Schleife wird n-mal auf dem ersten Index ausgeführt. und 0 danach. Also sollte das nicht O (2n) => O (n) sein?

Answer 1

Mein Verständnis ist, dass große O-Notation verwendet wird, um eine obere Grenze oder ein Worst-Case-Szenario zu geben. Die Frage, die Sie selbst stellen müssen, ist: Könnte der Eingabevektor n Werte haben, so dass zumindest in einem Fall für alle Werte im Eingabevektor n die while-Schleife vollständig ausgeführt wird? Dann wäre eine korrekte Big-O-Notation O (N^2), wenn nicht aber nahe, dann wäre O (N^2) immer noch eine bessere Schätzung als O (N), als O (N) für eine obere Grenze wäre schon überschritten worden.

Nachdem Sie die Frage bearbeitet und weitere Informationen dazu gegeben haben, stimme ich Ihnen zu. Es ist O (N)