Was ist die richtige große O-Notation für einen Algorithmus, der in triangular Zeit läuft? Hier ein Beispiel:Große O-Notation für Dreieckszahlen?
func(x):
for i in 0..x
for j in 0..i
do_something(i, j)
Mein erster Instinkt ist O(n²), aber ich bin nicht ganz sicher.
Ja, N * (N + 1)/2, wenn Sie die Konstanten und Terme niedrigerer Ordnung löschen, bleibt N-Quadrat übrig.
Ja, O(n^2) ist definitiv richtig. Wenn ich mich richtig erinnere, ist O sowieso immer eine obere Grenze, also sollte O(n^3) IMO auch korrekt sein, so wie O(n^n) oder was auch immer. Jedoch scheint O(n^2) die engste zu sein, die leicht abzugsfähig ist.
Wenn Sie mathematisch darüber nachdenken, ist der Bereich des Dreiecks, das Sie berechnen, ((n+1)^2)/2. Dies ist also die Rechenzeit: O (((n + 1)^2)/2)
Die Rechenzeit erhöht sich für diesen Code um den Faktor N * (N + 1)/2. Dies ist im Wesentlichen O (N^2).
wenn der Eingang steigt von N bis 2N dann Zeit des Algorithmus ausgeführt wird von erhöhen t bis 4t
somit Laufzeit mit dem Quadrat der Eingangsgröße proportional ist
so ist Algorithmus O (n^2)
O (! n) behandelt Fälle für eine faktorielle Berechnung (Dreieckszeit).
Es kann auch als O (n^2) dargestellt werden, dies scheint etwas irreführend zu sein, da die auszuführende Menge immer halb so groß ist wie O (n^2).
Per Definition, O (0.5 * n^2) == O (n^2) '(eine Gleichheit, die für jeden konstanten Faktor ungleich Null tatsächlich gilt), so ist dies aus einer rein theoretischen Perspektive nicht irreführend. :-) – Gijs
-1. A [Factorial] (http://en.wikipedia.org/wiki/Factorial) ist nicht dasselbe wie eine [Dreieckszahl] (http://en.wikipedia.org/wiki/Triangular_number). – gilly3
Sie haben Recht ... O ((n + 1) wählen Sie 2) = O (n^2) per Definition. – Protostome