Wenn... (war: LAUFZEIT. nächstes mal bitte weniger aussagekräftige titel wählen)

CStoll

O(f) bedeutet, daß der Algo maximal a*f(n) benötigt, um einen Input der Größe n zu berechnen.

Also in deinem Fall:
Laufzeit für n=30N ≤ a*log(n) = a*log(30N) = a*(log(30)+log(N)) = a*log(N)+C = Laufzeit für N + einen konstanten Wert

(genauer kannst du das mit der O-Notation nicht abschätzen)

Lest euch mal den Titel durch...das ist ne Verarsche. (und niemand hat den Beitrag editiert)

GuybrushThreepwood

CStoll schrieb:

(genauer kannst du das mit der O-Notation nicht abschätzen)

Mit einem gegebenen N kann man mit der O-Notation den Aufwand für 30N nicht genauer abschätzen, als daß der Aufwand für 30N größer ist als für N?
Wofür soll das ganze dann gut sein, nur um eine so triviale Aussage zu produzieren?

Du kannst immerhin noch abschätzen, daß die Zeitdifferenz zwischen N und 30N konstant ist, egal wie groß N wird (wenn du die Größe des Proportionalitätsfaktors a kennst, kannst du diese Differenz auch ausrechnen Δt=a*log30)

Und außerdem dient die O-Notation nicht für exaktere Werte, sondern um die Laufzeit zweier Algorithmen qualitativ zu vergleichen: Bespielsweise benötigt lineare Suche im Mittel O(n) (doppelte Eingabegröße -> doppelte Laufzeit), binäre Suche O(log n) (doppelte Eingabegröße -> ein zusätzlicher Vergleich).

GuybrushThreepwood

CStoll (off) schrieb:

Du kannst immerhin noch abschätzen, daß die Zeitdifferenz zwischen N und 30N konstant ist, egal wie groß N wird (wenn du die Größe des Proportionalitätsfaktors a kennst, kannst du diese Differenz auch ausrechnen Δt=a*log30)

Wenn ich für die Berechnungen/Zeitmessungen immer die selbe Maschine verwende, müßte ja a=1 sein. (oder woher kommt das a?). Also müsste demzufolge der Zeitunterschied zwischen 30N und N immer gleich log(30) Sekunden sein, egal wie viele Elemente der Algorithmus verarbeiten muß!? Das klingt aber nicht mehr nach einem log(n) Laufzeitverhalten.

CStoll (off) schrieb:

Und außerdem dient die O-Notation nicht für exaktere Werte, sondern um die Laufzeit zweier Algorithmen qualitativ zu vergleichen.

Also müsste es doch möglich sein zu sagen: wenn der Algorithmus 30 mal mehr Elemente bekommt, braucht er dafür x mal so lange!?

Das a hängt nicht nur von der Maschine ab, sondern auch vom Algorithmus. Z.B. benötigt die binäre Suche log[2] n Vergleiche - d.h. a wäre (ca.) die Zeit, die du für einen Schlüsselvergleich benötigst.

(Zeit O(1) bedeutet, daß du die Lösung in einer festgelegten Zeit hast, egal wie groß deine Eingabe ist)

Also müsste es doch möglich sein zu sagen: wenn der Algorithmus 30 mal mehr Elemente bekommt, braucht er dafür x mal so lange!?

Kann man doch auch: Wenn der Algorithmus 30 mal so viele Elemente bekommt, braucht er dafür C Sekunden zusätzlich (dieses C ist unabhängig von N und kann mit der O-Notation nicht genauer bestimmt werden) - das ist ein ganzes Stück besser als "x-fache Zeit"

GuybrushThreepwood

CStoll (off) schrieb:

(Zeit O(1) bedeutet, daß du die Lösung in einer festgelegten Zeit hast, egal wie groß deine Eingabe ist)

Oh ja, Fehler meinerseits.

CStoll (off) schrieb:

Kann man doch auch: Wenn der Algorithmus 30 mal so viele Elemente bekommt, braucht er dafür C Sekunden zusätzlich (dieses C ist unabhängig von N und kann mit der O-Notation nicht genauer bestimmt werden)

Ein Algorithmus mit der Laufzeit log(n) soll für eine x mal größere Eingabe eine nicht abschätzbare Zeit C, die auch noch unabhängig von der Größe der Eingabe ist, länger brauchen? Fällt mir schwer, das zu glauben.

GuybrushThreepwood

CStoll (off) schrieb:

... C Sekunden zusätzlich [...] - das ist ein ganzes Stück besser als "x-fache Zeit"

Wieso denn? Wenn ich C nicht kenne, bin ich genau so weit wie wenn ich x nicht kenne.

GuybrushThreepwood schrieb:

Ein Algorithmus mit der Laufzeit log(n) soll für eine x mal größere Eingabe eine nicht abschätzbare Zeit C, die auch noch unabhängig von der Größe der Eingabe ist, länger brauchen? Fällt mir schwer, das zu glauben.

OK, zurück zum Beispiel "binäre Suche" - für eine doppelt so große Eingabe (x=2) benötigt der Algorithmus genau EINEN zusätzlichen Vergleich, um deinen Schlüssel zu finden (C=t_vergl).

Und in einem konkreten Beispiel-Algorithmus hast du auch nicht nur die O(f)-Aussage, sondern eine etwas genauere Aschätzung, z.B. T_BS(n)=t_vergllog₂n - damit kommst du auf C=T(30N)-T(N)=1µslog₂30≈5t_vergl.

Zum Vergleich höhere Komplexitäten

Lineare Zeit - Doppelte Eingabegröße -> Doppelte Laufzeit
Polynomielle Zeit - Doppelte Eingabegröße -> Laufzeit *2^k
Exponentielle Zeit - Eingabe +C Elemente -> Laufzeit *x (=k*2^C)

hi,

danke @CStoll, das hat mich bestätigt.

volkard schrieb:

kommt drauf an, zu welcher basis der logarithmus ist.

wieso? es ging nur ums prinzip.

noch ein problem habe ich damit, dass die 8 sekunden gerade für ein n gemessen wurden, bei dem T(n) << k*log(n) ist. dann kann ich so gut wie keine vorhersage machen. aber das ist eher zweitrangig.