Was ist das große O, Obergrenze dieses Codes

Question

Ich bin ein wenig verwirrt, ich habe große O Zeit Komplexität für ein paar Stunden jetzt erforscht und lesen Sie alle Artikel hier.

Ich habe dieses Stück Code mir präsentiert, und ich möchte die obere Grenze dieses Codes finden.

Nun, aus dem, was ich bisher gelernt habe, würde ich annehmen, dass die obere Grenze O (n^2) ist, weil dies eine verschachtelte Schleife ist. Weil J jedoch mit I verbunden ist; Ich frage mich, ob dieser Code tatsächlich O (n log n) ist, ich muss sagen, dass ich das Konzept von O (n log n) nicht vollständig verstehe. Aber ich verstehe alle anderen Notationen wie ... O (1), O (n), O (log n), O (n^2), O (n!).

Answer 1

Für jede Iteration der äußeren Schleife, die innere Schleife genau i mal.

Wenn i = 0, läuft die innere Schleife 0 mal.

Wenn i = 1, wird die innere Schleife 1 Mal ausgeführt.

Wenn i = 2, läuft die innere Schleife 2 mal.

...

Wenn i = n-1, wobei die innere Schleife n-1 mal ausgeführt wird.

Also die Gesamtzahl der Male, die die innere Schleife läuft = 0 + 1 + 2 + ... + (n-1) = (n * (n-1))/2 = (n^2- n)/2.

Daher ist die Gesamtzahl der Berechnungen beteiligt = (n^2 - n)/2.

So wird die Zeitkomplexität des gegebenen Code = O (n^2).

Answer 2

Die Antwort ist O (n^2).

Stellen Sie sich vor, dass die Variable i die Zeilennummer einer Matrix und j die Spaltennummer ist. Mit dieser Schleife betrachten Sie nur die Hälfte der Matrix. Dies gibt Ihnen eine zeitliche Komplexität von O (0.5n^2), aber das ist nur O (n^2).

Um zu versuchen, Hilfe Sie O verstehen (n log (n)):

Ein Beispiel eines O (log (n)) Komplexität Algorithmus auf einer sortierten Liste von Zahlen eine binäre Suche ist. Sie setzen das halbe Problem bei jedem Vergleich fest, indem Sie das mittlere Element überprüfen und die Hälfte der Liste verwerfen, die deutlich über oder unter der von Ihnen betrachteten Zahl liegt.

Die gleiche binäre Suche auf n verschiedenen Sätzen, die alle Länge n sind, hätte Zeitkomplexität O (n log (n)).

Answer 3

Inner Loop beginnt iteriert i mal, und i erhöht sich um 1 gesteuert durch die äußere Schleife.

Deshalb ist die innere Schleife erhalten 1, 2, 3, ..., n durch die äußere Schleife und iterieren, die an der Innenschleife 1 + 2 + 3 + ... + n = n(n+1)/2

n(n+1)/2 = (n^2)/2 + n/2 Iterieren läuft darauf hinaus. Das Wachstum dieser Funktion wird von n^2 dominiert, daher kann die obere Grenze als O(n^2) angegeben werden.

Überprüfen Sie die Simulationen, die ich gerade ausgeführt habe.