Big O Notation eines Ausdrucks

Question

Wenn ich einen Algorithmus, die 4n ^ 2 + 7n bewegt braucht, um zu erreichen, was ist ihr O? O (4 N ^ 2)? O (n ^ 2)?

Ich weiß, dass 7n abgeschnitten ist, aber ich weiß nicht, ob ich das n ^ 2 Koeffizient halten soll oder nicht.

Danke

Answer 1

Sie sollten alle Koeffizienten fallen, weil die Frage wirklich fragt, „in der Größenordnung von“, die sie als linear zu charakterisieren versucht, exponentiell, logarithmisch, etc ... Das heißt, wenn n sehr groß ist, der Koeffizient von wenig Bedeutung.

Dies erklärt auch, warum Sie die + 7n fallen, denn wenn n sehr groß ist, dass Begriff relativ wenig Bedeutung für die endgültige Antwort hat. Wenn Sie mit Kalkül vertraut sind, könnte man sagen Sie lim n-> inf (4 * n ^ 2 + 7n) ~ = lim n-> inf (4 * n ^ 2) ~ = lim n-> inf (n ^ 2)

Sie können auch über diesen in einem grafischen Sinne denken ... das heißt, wenn Sie die Funktion 4n Graph ^ 2 + 7n für größere und größere Werte von n, könnte ein Mathematiker sagen: „Es sieht aus wie n ^ 2“. Zugegeben, hätte es ein ziemlich liberal Mathematiker sein, da dies nicht eine strenge Aussage ist, aber das ist im Grunde, was O (...) zu vermitteln versucht.

Answer 2

Die Koeffizienten sind nicht relevant in Big O-Notation, es ist also nur O (n ² ). Wie Wikipedia erklärt :

  

[...] die Koeffizienten werden irrelevant, wenn wir zu jeder anderen Ordnung des Ausdrucks zu vergleichen, wie ein Ausdruck, der einen Term enthält, n ³ oder n ² .

Answer 3

Jedes Lesen oder Schreiben über die Komplexität von Algorithmen sollte genau wissen, was die Landau Symbole und < a href = „http://mathworld.wolfram.com/AsymptoticNotation.html“ rel = „nofollow noreferrer“> asymptotische Notationen sind, sonst nicht wirklich sie verstehen, was los ist, oder einfach nur eine ungefähre haben (und oft irreführend) Idee.

(viel) zu vereinfachen, lassen f und g zwei Funktionen f : N -> N und g : N -> N sein. Wir sagen, dass f is O(g), wenn und nur wenn es eine Konstante M > 0 so dass |f(n)| < M|g(n)|, für alle n > M. Das heißt, mehr informell, von einem großen Wert von n beginnen, alle Werte f(n) kleiner sind als ein Vielfaches von g(n) (dh g wächst schneller als f).

Diese Definition entspricht

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

Also, lassen Sie uns f(n) = 4n^2 + 7n und g(n) = n^2 und versuchen f is O(g) zu beweisen (Ich werde {n -> +oo} weglassen):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

Dies bedeutet, dass es eine M so dass n > M ==> |f(n)| < M|g(n)| und damit f is O(g).

So technisch ist es richtig 4n^2 + 7n is O(4n^2) zu sagen, wie es richtig ist, 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n) zu sagen, und so weiter. Aber sinnvoll zu sein, sind wir in der interessierte untere Grenze. Also, wenn f is O(e^n) und f is O(n^2), wir sind mehr daran interessiert, in das f is O(n^2) zu wissen, da dies wesentlich restriktiver ist.

Sehr wichtiger Hinweis

Was ist extremelly wichtig, wenn ein Algorithmus der Wahl ist zu verstehen, dass big-O Notationen bezieht sich auf asymptotisch Fälle , das heißt, wenn man bedenkt, extrem, unvorstellbar große Eingänge , das kann im bekannten Universum (von {n -> +oo} dh unendlichen Eingangssätze, mathematisch ausgedrückt) über die Rechenleistung geht ebenfalls zur Verfügung.

Für praktische Anwendungen (dh nicht so große Eingänge), wenn ein Algorithmus die Wahl, sicher, werden Sie Kandidat Algorithmen beobachten big-O Notationen , aber Sie müssen sein sicher, dass der gewählte Algorithmus ist gut angepasst (und eine bessere Leistung) für Ihre (erwarteten) Eingang.

Schließlich, in der Regel eine bessere Durchführung Algorithmen sind schwieriger zu verstehen und richtig zu implementieren. Sie müssen diese Tatsache auch berücksichtigen, wenn ein Algorithmus die Wahl (dh ist die Zeit, die ich verbringen Debuggen und meine Implementierung Festsetzung dieses Algorithmus wesentlich besser als die Zeit würde ich mit einem anderen warten müssen Algorithmus, mit einer schlechteren big-O-Notation? . Wenn dem so ist, sollten Sie die einfacheren, weniger effizienten Algorithmus betrachten, da die Gesamtlösung effizienter wäre).

Answer 4

Es ist O (n ^ 2). Konstante Faktoren „Einzug in das O“. Sie halten nur den größten Exponenten, da dies der einzige dominierende ist. Und Sie können Koeffizienten auslassen, da, wenn in kleineren Gesamtzahlen verschiedene Algorithmen auch sehr große Koeffizienten führen den Vergleich als einen größeren Exponenten (mit n groß genug ist).

Answer 5

Eine Aussage wie

4n² + 7n = O(n²)

bedeutet, dass für einen konstanten Multiplikator c, der Ausdruck cn² wird schließlich Überholmanöver 4n² + 7n. Es ist technisch nicht falsch, die Koeffizienten in dort zu lassen - O(n²) und O(4n²) genau dasselbe bedeuten, weil jede Konstante c für die ehemaligen kann durch c/4 für letztere ersetzt werden. Doch so etwas ist weniger klar, möglicherweise irreführend, und definitiv nicht dem Standard entsprechende.

Answer 6

Mathematisch gesprochen, würden Sie schreiben O (4n²). Es bedeutet, dass die Komplexität Funktion Ihrer Algorithmen verhält sich wie n-> 4n² auf positive unendlich.

Aber in der Informatik / Algorithmus, würden Sie nur schreiben O (n²), die ausreichend ist, Ihren Algorithmus zu kategorisieren.