O (n) + O (n) = O (n)?
Laut Alex Martelli in O'Reillys Python in Kürze, die Komplexitätsklasse O(n) + O(n) = O(n) . Also ich glaube es. Aber bin verwirrt. Er erklärt es, indem er sagt, dass "die Summe zweier linearer Funktionen von N auch eine lineare Funktion von N ist."
Laut wikipedia ist in der funktionalen Analyse eine lineare Funktion eine lineare Karte, ein Beispiel dafür wäre f(x+y) = f(x) + f(y) . Gefunden, was scheint eine einfachere Definition hier einfach zu sagen, "eine lineare Funktion ist eine Funktion wer ist Graph ist eine gerade Linie. " Und es enthält ein paar weitere Beispiele, die weniger esoterisch aussehen als die Wikipedia Artikel.
und:
%Vor%Vielleicht wäre es fair zu erwarten, dass die Summe zweier linearer Gleichungen in einem Graphen als eine gerade Linie dargestellt werden könnte, die etwas Ähnliches wie einen Durchschnitt zwischen den geraden Linien zeigt, die jeden repräsentieren würden .
So verstehe ich richtig, dass, obwohl in den folgenden zwei Funktionen die "komplexe" Funktion dreimal so lange dauert wie die "einfache", sie alle in der großen O-Notation als O (n) funktionieren, weil der Bogen der Verarbeitungszeit durch eine gerade, diagonale Linie auf einem Diagramm dargestellt würde, und der Zeitunterschied würde durch die Tatsache dargestellt, dass in einer graphischen Darstellung der Winkel der komplexeren Funktion schärfer wäre / p> %Vor%
8 Antworten
Die Aussage ist richtig, weil die Addition zweier linearer Funktionen ebenfalls eine lineare Funktion ist. Nehmen Sie zum Beispiel diese beiden:
%Vor%Fügen Sie sie zusammen und Sie erhalten:
%Vor%Was auch eine lineare Funktion ist! Dies gilt für zwei lineare Funktionen.
%Vor%Auch wenn in den folgenden zwei Funktionen die "komplexe" Funktion dreimal so lange zu verarbeiten ist wie die "einfache", funktionieren sie in der Groß-O-Notation als O (n), weil der Bogen der Verarbeitungszeit würde durch eine gerade, diagonale Linie auf einem Diagramm dargestellt werden, obwohl der Winkel der komplexeren Funktion schärfer wäre?
Ja. Der Buchstabe O wird verwendet, weil er sich auf die Reihenfolge einer Funktion bezieht. Lineare Funktionen haben die gleiche Reihenfolge , O(n) , O(3n) , O(Cn) sind alle linear.
Andererseits sind O(n^2) , O(n^3) und O(n^C) alle Polynomfunktionen (Grad 2, 3, C). Hier (im Umgang mit Algorithmen) beginnen wir oft mit zwischen Dingen wie O(n^2) und O(n^5) zu unterscheiden - obwohl sie beide in der gleichen Reihenfolge sind.
Und O(2^n) , O(3^n) und O(C^n) sind exponentiell. Im Allgemeinen möchten Sie keinen Algorithmus mit exponentieller Komplexität (oder schlechter) schreiben.
Ein guter (der beste?) Weg, dies zu tun, ist, sich auf die mathematische Definition von big-O zu beziehen:
Im Klartext:
Diese beiden Aussagen sind äquivalent:
f ist O (g)
Das Verhältnis f (n) zu g (n) als n Erhöhungen tendieren zu einem nicht negativen Wert.
In unserem Fall haben wir g (n) = n . Wenn wir nun f (n) = f 1 (n) + f2 (n) annehmen und annehmen Sowohl f 1 als auch f 2 sind < em> O (n) ist die obige Grenze gleich α = α 1 + α 2 die selbst größer oder gleich null sein muss (da definitionsgemäß α 1 ≥ 0 und α 2 ≥ 0 ). Daher ist f 1 <(n) + f2 (n) auch O (n) , nach unserer Definition.
Ja, das liegt daran, dass die Big-O-Notation nicht für die Berechnung der absoluten Laufzeit gedacht ist, sondern um das Verhalten von Algorithmen mit wachsender Eingabe zu beschreiben.
Mit anderen Worten, wenn Sie ein Algo haben, das in O(3n) und O(n) funktioniert und Sie n erhöhen, möchten Sie beide, dass sie so viel länger laufen.
Es gibt nur eine Vorstellung davon, ob ein Algorithmus einen anderen zu einem bestimmten Zeitpunkt überstreichen wird.
Natürlich kann mathematisch alles mit Definitionen bewiesen werden.
Das ist richtig. Solange die Linie in der Grafik gerade ist, ist die Funktion O (n), unabhängig vom Winkel. Eine Funktion nimmt lineare Zeit, wenn Sie sagen können "diese Funktion dauert x Sekunden für jedes Eingabeelement." x könnte in diesem Fall drei oder neun oder eine Million sein, und es ist immer noch eine lineare Funktion.
Schon jetzt gibt es viele gute Antworten, aber ich habe aus diesem Blickwinkel keine Antwort gesehen. Die Summe von O (x) + O (y) ist die schlechteste von O (x) und O (y). In diesem Fall, da beide linear sind, sagen x = C1n und y = C2n und C1 & gt; C2. Somit dominiert x die Funktion O () und das große O wird O(C1n) => O(n)