Der Unterschied zwischen theoretischer Komplexität und praktischer Effizienz

Wenn ich diesen Pseudocode habe:

for i=0 to n/2 do
   for j=0 to n/2 do 
       ... do anything ....

Die Anzahl der Iterationen beträgt $n^2/4$.

Was ist die Komplexität dieses Programms? Ist es$O(n^2)$?

Was ist die formelle / informelle Intuition für welche Komplexität?

Als nächstes, wenn ich diesen anderen Pseudocode habe:

for i=0 to n do
   for j=0 to n do 
       ... do anything ....

Die Komplexität ist wieder $O(n^2)$ -- Ist das korrekt?

Gibt es in diesem Fall einen Unterschied zwischen Effizienz in der Praxis und theoretischer Komplexität? Ist einer davon schneller als der andere?

Big O formal

$O(f(n)) = \{g(n) | \exists c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) \leq c*f(n)\}$

Big O Informell

$O(f(n))$ ist der Satz von Funktionen, die langsamer (oder gleich schnell) wachsen als $f(n)$. Dies bedeutet, dass jede Funktion, aus der Sie auswählen$O(f(n))$Nennen wir sie $g(n)$, und Sie wählen eine ausreichend große $n$, $f(n)$ wird größer sein als$g(n)$. Oder mit anderen Worten:$f(n)$ wird irgendwann jede Funktion in übertreffen $O(f(n))$ wann $n$ wird größer. $n$ ist die Eingabegröße Ihres Algorithmus.

Als Beispiel. Lass uns auswählen$f(n) = n^2$.

Wir können das sagen $f(n) \in O(n^3)$. Beachten Sie, dass wir im Laufe der Zeit den Missbrauch von Notationen zugelassen haben, sodass fast jeder schreibt$f(n) = O(n^3)$ jetzt.

Normalerweise betrachten wir bei der Bewertung von Algorithmen deren Reihenfolge. Auf diese Weise können wir vorhersagen, wie sich die Laufzeit des Algorithmus erhöht, wenn die Eingabegröße ($n$) erhöht sich.

In Ihrem Beispiel sind beide Algorithmen in Ordnung $O(n^2)$. Ihre Laufzeit erhöht sich also auf die gleiche Weise (quadratisch) wie$n$erhöht sich. Ihr zweiter Algorithmus ist viermal langsamer als der erste, aber das interessiert uns normalerweise nicht ** theoretisch *. Algorithmen mit derselben Reihenfolge können unterschiedliche Faktoren haben ($c$in der formalen Definition) oder andere Begriffe niedrigerer Ordnung in der Funktion, die die Anzahl der Schritte bewertet. Aber normalerweise liegt das an den Implementierungsdetails, und das interessiert uns nicht.

Wenn Sie einen Algorithmus haben, der ausgeführt wird $O(log(n))$ Zeit können wir sicher sagen, dass es schneller sein wird als $O(n)$ [1] weil $log(n) = O(n)$. Egal wie schlimm das ist$O(log(n))$ Der Algorithmus ist implementiert, egal wie viel Overhead Sie in den Algorithmus stecken, er ist immer [1] schneller als der $O(n)$Algorithmus. Auch wenn die Anzahl der Schritte in den Algorithmen ist$9999*log(n) = O(log(n))$ und $0.0001*n = O(n)$, das $O(log(n))$ Algorithmus wird schließlich schneller sein [1].

Aber vielleicht in Ihrer Bewerbung, $n$ ist immer niedrig und wird nie groß genug sein, so dass die $O(log(n))$Algorithmus wird in der Praxis schneller sein . Also mit dem$O(n)$ Der Algorithmus führt trotz allem zu schnelleren Laufzeiten $n = O(log(n))$

[1] wenn $n$ ist ausreichend groß.

Auberon bot eine sehr gute Erklärung des Big O . Ich werde versuchen zu erklären, was das für Sie bedeutet.

Erstens hast du recht. Das erste Codebeispiel hat$\frac{n^2}{4}$Iterationen, ist aber immer noch in der Komplexitätsklasse O(n^2).

Warum?

Die Sache mit Komplexitätsklassen ist, dass wir davon ausgehen, dass es für die Laufzeit nicht so schlecht ist, etwas mehrmals zu tun .

Stellen Sie sich einen Algorithmus mit Komplexität O(2^n)für den Betrieb n=3und unter 1 Sekunde.

Wir könnten dies 10 Mal ausführen und nach etwa 10 Sekunden immer noch eine Antwort erwarten.

Stellen Sie sich nun vor, Sie erhöhen sich num 10. Das Programm 2^10=1024dauert Sekunden.

Die Informatiker sagten also im Grunde: " Mann, führende Faktoren sind ärgerlich. Nehmen wir einfach an, dass n bis unendlich wächst und vergleichen wir dort die Funktionen. "

Was zum Big O führte .

In der Praxis

In der Praxis ist es sehr gut möglich, dass eine Lösung mit viel geringerer Komplexität viel schneller läuft (für "kleine" Eingaben). Es ist leicht, sich ein Programm vorzustellen, das ausgeführt wird, O(n)aber 10^10*nIterationen benötigt .

Es ist O (n), aber selbst eine O(2^n)Lösung könnte für kleine n schneller sein.

Zusammenfassend:

Das Big O ist ein nützliches Werkzeug. Sie müssen jedoch noch darüber nachdenken, wie schnell Ihr Algorithmus in der Praxis ist, da er nur beschreibt, wie viel Zeit er benötigt, wenn die Eingabe wächst.

Wenn ich diesen Pseudocode habe:

for i=0 to n/2 do
   for j=0 to n/2 do 
       ... do anything ....

Die Anzahl der Iterationen beträgt $n^2/4$.

Eigentlich ist es $(1+n/2)^2 = n^2/4 + n + 1$.

Was ist die Komplexität dieses Programms? Ist richtig$O(n^2)$?

Das hängt ganz davon ab, was "alles tun" ist. Zum Beispiel, wenn "irgendetwas tun" durch die Zeile ersetzt wird

for k=0 to 2^n do {}

dann ist die Laufzeit $\Theta(n^22^n)$.