O-Notation: O(N²+N)? - ich denke nicht ...
-
hallo,
ich muss zu diesem codefragment die O-Notation angeben:
// Fragment 3 int diff, sum = 0; for (int i=0; i<n*n; i++) sum++; for (int j=0; j<n; j++) diff--;ich komme zu entweder O(N²) oder O(N²+N), was beides falsch ist, denke ich mal.
kann mir jemand helfen, vllt. einen denkanstoss geben?
Vielen Dank im Voraus!
mfg,
julian
-
// Fragment 3 int diff, sum = 0; for (int i=0; i<n*n; i++)//O(n^2) sum++; for (int j=0; j<n; j++)//O(n)) diff--;soweit warst du sicher auch schon
Wir haben also O(n2)+O(n)=O(n2) (wegen definition)
//fixed typo
-
ich komme zu entweder O(N²) oder O(N²+N), was beides falsch ist, denke ich mal.
Beide sind gleich und beide richtig.
-
Hallo,
O(n^2) (= O(2n^2 = O(n^2 + n)) stimmt.
Chris
-
Du nimmst immer nur das höchste Polynom von N ohne Vorfaktoren.
Man möchte damit nur das Verhalten (z.B. linear, quadratisch ect.) sehen.
Allerdings bleibt z.B. N*log(N) so stehen
-
Hallo,
allgemeiner kann man sagen, dass eine Komplexitätsklasse "gleich" mit einer anderen ist, wenn du zwei Faktoren findest, die- wenn du sie mit der einen multiplizierst- dazu führen, dass die andere ffa (also ab einem n0 aus IN) Elemente dazwischen eingeschlossen wird.
Um zu zeigen, dass n^2 = n^2 + n ist, wählst du z.B. 1 und 2, dann gilt ab n0 = 2:
1 * n^2 < n^2 + n < 2 * n^2Chris
-
vielen dank an alle fuer die hinweise und erklaerungen!
ich denke, ich habe es jetzt verstanden.mfg,
julian
-
Simonek schrieb:
Allerdings bleibt z.B. N*log(N) so stehen
Und was ist da so verwunderlich dran, dass Du es extra erwähnst?
-
das könnte man kreativerweise als polynom interpretieren.