Ich habe über große O-Notation gelesen. Es heißt,
Der große O einer Schleife ist die Anzahl der Iterationen der Schleife in Anzahl der Anweisungen innerhalb der Schleife.
Hier ist ein Code-Snippet,
%Vor%Nach der Definition sollte das große O nun O (n * 2) sein, aber es ist O (n) . Kann mir jemand helfen, indem er erklärt, warum das so ist? Danke im Voraus.
Wenn Sie die Definition der O () -Notation überprüfen, werden Sie feststellen, dass (Multiplikator-) Konstanten keine Rolle spielen.
Die Arbeit innerhalb der Schleife ist nicht 2. Es gibt zwei Anweisungen, für jede von ihnen müssen Sie ein paar Maschinenanweisungen machen, vielleicht ist es 50 oder 78 oder was auch immer , aber das ist für die asymptotischen Komplexitätsberechnungen völlig irrelevant, weil sie alle Konstanten sind. Es hängt nicht von n ab. Es ist nur O (1).
O (n) wird verwendet, um die Schleife gegen eine mathematische Funktion zu messen (wie n ^ 2, n ^ m, ..).
Wenn Sie also eine Schleife wie diese haben
%Vor%Die beste mathematische Funktion, die die Schleife benötigt, wird mit O (n) berechnet (wobei n eine Zahl zwischen 0..infinity ist)
Wenn Sie eine Schleife wie diese haben
%Vor%Bedeutet, dass es O (n * 2) benötigt; mathematische Funktion = n * 2
%Vor%Diese Schleife benötigt O (n ^ 2) Zeit; mathematische Funktion = n ^ n Auf diese Weise können Sie berechnen, wie lange Ihre Schleife für n 10 oder 100 oder 1000 benötigen
Auf diese Weise können Sie Diagramme für Schleifen und ähnliches erstellen.
Nennen Sie es nicht "das große O". Das ist falsch und irreführend. Was Sie wirklich zu finden versuchen, ist asymptotisch wie viele Befehle als Funktion von n ausgeführt werden. Der richtige Weg, über O (n) nachzudenken, ist nicht eine Funktion, sondern eine Reihe von Funktionen. Genauer gesagt:
O (n) ist der Satz aller Funktionen f (x), so dass es eine Konstante M und eine Anzahl x_0 gibt, wobei für alle x & gt; x_0, f (x) & lt; M x.
Mit anderen Worten, wenn n sehr groß wird, wird das Wachstum der Funktion (zum Beispiel die Anzahl der Anweisungen) zu einem bestimmten Zeitpunkt durch eine lineare Funktion mit einem konstanten Koeffizienten begrenzt.
Abhängig davon, wie Sie Anweisungen zählen, kann die Schleife eine andere Anzahl von Anweisungen ausführen, aber egal, was sie nur n mal iteriert. Daher ist die Anzahl der Anweisungen in O (n). Es spielt keine Rolle, ob es 6n oder .5n oder 100000000n mal wiederholt, oder sogar wenn es nur eine konstante Anzahl von Anweisungen ausführt! Es ist immer noch in der Klasse von Funktionen in O (n).
Um ein wenig mehr zu erweitern, ist die Klasse O (n * 2) = O (0,1 * n) = O (n), und die Klasse O (n) ist strikt in der Klasse O (n ^ 2) enthalten. Infolgedessen ist diese Schleife auch in O (2 * n) (weil O (2 * n) = O (n)) und in O (n ^ 2) enthalten (aber diese Obergrenze ist nicht eng).
Die Big-O-Notation ignoriert konstante Multiplikatoren (und zwar per Definition), also ist O (n) und O (2n) genau dasselbe. Wir schreiben normalerweise O (n), weil das kürzer und vertrauter ist, aber O (2n) bedeutet dasselbe.
O (n) bedeutet, dass die Komplexität der Schleifenzeit linear mit der Anzahl der Elemente zunimmt.
2 * n ist immer noch linear, also sagen Sie, dass die Schleife der Ordnung O (n) entspricht.
Die von Ihnen gepostete Schleife ist jedoch O (n), da die Anweisungen in der Schleife konstante Zeit benötigen. Zweimal ist eine Konstante immer noch eine Konstante.
Normalerweise drückt big O Notation die Anzahl der Hauptoperationen in einer Funktion aus.
In diesem tou're, das über n Elemente übersprudelt. Komplexität ist also O (n) .
Sicher ist nicht O (n ^ 2) , da quadratisch die Komplexität dieser Algorithmen ist, wie bubble sort, die jedes Element in der Eingabe mit allen anderen Elementen vergleicht.
Wie Sie sich erinnern, bubble sort, um die richtige Position zu bestimmen, an der ein Element eingefügt werden soll, vergleichen Sie jedes Element mit den anderen n in einer Liste (sprudelndes Verhalten).
Sie können höchstens behaupten, dass Ihr Algorithmus komplex ist O (2n) , da er für jedes Element in der Eingabe zwei Phrasen ausgibt, aber in big O notation O (n) ist gleich O (2n).
Tags und Links big-o