Angabe asymptotische Laufzeit: ist dieser Fall Auslegungssache?
-
Hallo,
bezüglich asymptotischer Laufzeit von Algorithmen:
Man nehme ein Bild der Breite n und Höhe n und eine Funktion f, welche jeden Pixel transformiert (z.B. in Graustufenwert umwandelt).f: BILD -> BILD, f(b) = b' sei definiert durch
für x in [0,n]: für y in [0,n]: Transformiere Pixel in b(x,y) rückgabe b
Dann könnte man sagen, f hätte Laufzeit O(n*n) = O(n^2).
Allerdings könnte man auch sagen, die Laufzeit von f wächst linear mit der Anzahl der Pixel, also f = O(n).Steht mir das definitorisch frei oder gibt es da eine Faustregel, ob f = O(n) oder f = O(n^2) *?
*ja, mir ist bewusst dass f = O(...) schlampig ist, wird aber häufig so notiert.
-
Wenn n gegeben ist (wie in "Man nehme ein Bild der Breite n und Höhe n und eine Funktion f"), dann solltest du dich natürlich auch daran halten.
Wenn nichts gegeben ist, wähle ich n meistens so, dass die Eingabegrösse O(n) ist.
-
Du sagst, was n ist und schreibst dann das Laufzeitverhalten. Wo ist das Problem?
-
laufzeit0r schrieb:
Allerdings könnte man auch sagen, die Laufzeit von f wächst linear mit der Anzahl der Pixel, also f = O(n).
Falsch, denn die Anzahl der Pixel geht mit O(n^2). Dein n ändert hier plötzlich seine Bedeutung, wenn es auf einmal für die Anzahl der Pixel stehen soll.