Es gibt mehrere $O$ Notationen wie oder und so weiter. Ich habe mich gefragt, ob es in der Realität Variationen wie oder gibt oder ob diese mathematisch falsch sind.$O(n)$$O(n^2)$$O(2n^2)$$O(\log n^2)$

Oder wäre es richtig zu sagen, dass es möglich ist, ein zu einem zu verbessern ? Ich kann und muss noch keine Laufzeiten herausfinden und ich muss nichts verbessern, aber ich muss wissen, ob Sie so Ihre Funktionen in der Realität beschreiben.$O(5n^2)$$O(3n^2)$

Ich habe mich gefragt, ob es in der Realität Abweichungen von solchen wie $O(2n^2)$ oder $O(\log (n^2))$ gibt oder ob diese mathematisch falsch sind.

Ja, $O(2n^2)$ oder $O(\log (n^2))$ sind gültige Variationen.

Sie werden sie jedoch selten sehen, wenn Sie sie überhaupt sehen würden, insbesondere in den Endergebnissen. Der Grund dafür ist , dass $O(2n^2)$ ist , $O(n^2)$ . Ähnlich $O(\log (n^2))$ ist $O(\log n)$ . Für Anfänger mag das überraschend sein. Diese Gleichheiten sind jedoch mehr oder weniger der Grund, warum große $O$ Notationen eingeführt wurden, um einen multiplikativen konstanten Faktor zu verbergen, der oft schwer zu bestimmen und relativ unbedeutend ist.

Wäre es richtig zu sagen, dass es möglich ist, ein $O(5n^2)$ zu einem $O(3n^2)$ zu verbessern ?

Es ist überhaupt keine Verbesserung, wenn die zeitliche Komplexität eines Algorithmus von $O(5n^2)$ auf $O(3n^2)$ oder von $\Omega(5n^2)$ auf $\Omega(3n^2)$ geändert wird , weil $O(5n^2)$ ist , $O(3n^2)$ während $\Omega(5n^2)$ ist , $\Omega(3n^2)$ . Es ist also falsch zu sagen, dass die Zeitkomplexität von$O(5n^2)$ auf$O(3n^2)$ verbessert wird. Es ist richtig zu sagen, dass die zeitliche Komplexität eines Algorithmusnatürlichvon$5n^2$ auf$3n^2$ verbessert wird.

Aufgabe 1. Zeigen Sie, dass $O(5n^2)=O(3n^2)=O(n^2)$ .

Aufgabe 2. Zeigen Sie, dass $O(\log n)=O(\log (n^2))$ .

Aufgabe 3. Zeigen Sie, dass $\Omega(n^2+n)=\Omega(n^2)$ .

Es steht Ihnen jederzeit frei, diese Notation überhaupt nicht zu verwenden. Das heißt, Sie können eine Funktion $f(n)$ so genau wie möglich bestimmen und dann versuchen, diese zu verbessern. Beispielsweise könnten Sie einen Sortieralgorithmus haben, der $f(n)$ -Vergleiche durchführt, sodass Sie versuchen könnten, einen anderen Sortieralgorithmus zu finden, der nur $g(n)$ -Vergleiche durchführt. Natürlich existieren alle Arten von Funktionen $f(n)$ (theoretisch) und können auch (in der Praxis) auftreten.

Anstatt die Big Oh-Notation als mysteriöse Magie zu behandeln, bei der Sie Zauberer konsultieren müssen, um zu fragen, ob Sie etwas tun können, sollten Sie sich ihre Definition ansehen . Respektieren Sie die Definition und tun Sie dann alles, was Sie brauchen, um Ihre Arbeit zu erledigen.

Die akzeptierte Antwort ist zwar recht gut, berührt aber immer noch nicht den wahren Grund, warum $O(n) = O(2n)$ .

Die Big-O-Notation beschreibt die Skalierbarkeit

Im Kern beschreibt die Big-O-Notation nicht, wie lange die Ausführung eines Algorithmus dauert. Es ist auch keine Beschreibung, wie viele Schritte, Codezeilen oder Vergleiche ein Algorithmus durchführt. Dies ist am nützlichsten, wenn beschrieben wird, wie ein Algorithmus mit der Anzahl der Eingaben skaliert.

Nehmen Sie zum Beispiel eine binäre Suche. Wie finden Sie bei einer sortierten Liste einen beliebigen Wert darin? Nun, Sie könnten in der Mitte beginnen. Da die Liste sortiert ist, gibt der mittlere Wert an, in welcher Hälfte der Liste sich Ihr Zielwert befindet. Die Liste, die Sie durchsuchen müssen, wird nun in zwei Hälften geteilt. Dies kann rekursiv angewendet werden und dann in die Mitte der neuen Liste usw. verschoben werden, bis die Listengröße 1 beträgt und Sie Ihren Wert gefunden haben (oder er in der Liste nicht vorhanden ist). Durch Verdoppeln der Größe der Liste wird dem Algorithmus nur ein zusätzlicher Schritt hinzugefügt, bei dem es sich um eine logarithmische Beziehung handelt. Somit ist dieser Algorithmus $O(\log n)$. Der Logarithmus ist Basis 2, aber das spielt keine Rolle - der Kern der Beziehung besteht darin, dass das Multiplizieren der Liste mit einem konstanten Wert der Zeit nur einen konstanten Wert hinzufügt.

Vergleichen Sie eine Standardsuche mit einer unsortierten Liste. In diesem Fall können Sie nur nach einem Wert suchen, indem Sie jeden einzelnen überprüfen. Das schlimmste Szenario (was Big-O speziell impliziert) ist, dass Ihr Wert ganz am Ende steht, was bedeutet, dass Sie für eine Liste der Größe $n$$n$ Werte überprüfen müssen . Durch Verdoppeln der Größe der Liste wird die Anzahl der Überprüfungen verdoppelt. Dies ist eine lineare Beziehung. $O(n)$ . Aber selbst wenn Sie zwei Operationen für jeden Wert ausführen müssten, bleibt die lineare Beziehung bei einigen Verarbeitungsvorgängen bestehen. $O(2n)$ ist als Deskriptor einfach nicht nützlich, da es genau die gleiche Skalierbarkeit wie O beschreiben würde$O(n)$ .

Ich weiß zu schätzen, dass viele dieser Antworten Sie grundsätzlich dazu auffordern, selbst zu diesem Schluss zu kommen, indem Sie die Definition von Big-O lesen. Aber dieses intuitive Verständnis hat eine ganze Weile gedauert, bis ich meinen Kopf umwickelt habe, und deshalb habe ich es Ihnen so klar wie möglich dargelegt.

Sie können $O(f)$ für jede Funktion $f$ schreiben und es ist absolut sinnvoll. Gemäß der Definition ist $g(n)=O(f(n))$ wenn es eine Konstante $c$ so dass$g(n)\leq c\,f(n)$ für alle groß genug $n$ . Nichts in dieser Definition besagt, dass$f$ eine Art "nette" Funktion sein muss.

Wie andere Antworten gezeigt haben, beschreiben $g(n)=O(f(n))$ und $g(n)=O(2f(n))$ genau dieselbe Situation: wenn $g(n)\leq c\,f(n)$ für alle alle groß genug $n$ , dann haben wir auch$g(n)\leq \tfrac{c}{2}2f(n)$, also$g(n)=O(2f(n))$ (wobei die Konstante$c/2$ ).

Schreiben Sie als Nebenproblem nicht " $\log n^2$ ", da nicht 100% klar ist, was es bedeutet. Man könnte sagen, dass es offensichtlich bedeutet$\log(n^2)$ aber fast jeder würde das als$2\log n$ schreiben, so dass der Leser Zweifel hat.

$O$

Schauen Sie sich die Definition von O (f (n)) an und Sie sehen, dass zum Beispiel O (2n ^ 2) und O (n ^ 2) genau gleich sind. Das Ändern eines Algorithmus von 5n ^ 2 auf 3n ^ 2 Operationen ist eine 40-prozentige Verbesserung. Der Wechsel von O (5n ^ 2) zu O (3n ^ 2) ist eigentlich keine Änderung, sie sind gleich.

Lesen Sie erneut die Definition von O (f (n)).

$O(f(n)) = \lbrace g(n) | \exists n,c>0: \forall m > n: c\times g(m) \le f(m)\rbrace$

$=$$\in$

$O(n) = O(2n)$