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.

knivil

Du sagst, was n ist und schreibst dann das Laufzeitverhalten. Wo ist das Problem?

SeppJ

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.