Diskussion:Zeitkomplexität

Unter der Zeitkomplexität eines Problems versteht man die (minimale) Anzahl an Rechenschritten, ... Also das halte ich für ein Gerücht. Ein Algorithmus braucht für n Aktionen immer mindestens O(1), ob er nun etwas tut oder nicht. Steht - zumindest in der Informatik - O nicht eher für die maximale Anzahl? --Bodo Thiesen 06:24, 14. Dez 2004 (CET)

Wie schaffst Du denn n Aktionen in O(1)? Selbst wenn jede dieser Aktionen in konstanter Zeit (also O(1)) machbar ist, brauchst Du $n\cdot O(1)=O(n)$ für n Aktionen. Mit der O-Notation wird in der Informatik eine Funktion angegeben, die mindestens genauso stark wächst, wie das, was man abschätzen möchte (in diesem Fall also die Laufzeit Deines Algorithmus). Siehe auch Landau-Symbole. --Pinguin.tk 13:54, 14. Dez 2004 (CET)

int fake_strlen(char * string) { return 42; }

Laufzeitkomplexität? Richtig, O(1) und nicht O(n). Jeder Algorithmus ist mindestens O(1). Die meisten sind selbstverständlich komplexer, aber O(1) ist jeder (mindestens). Und die Formulierung von oben interpretiere ich so, daß ich einfach für einen gegebenen Algorithmus sage "Jo, der beaucht mindestens Zeit für Pro- und Epilog, und macht dann auch noch irgendwas, also ist er mindestens O(1)", und kann dann diesen Algorithmus ohne weitere Betrachtung als O(1) einstufen. Das ist selbstverständlich nicht richtig, aber das ist die Aussage des Satzes. Ich meine, es wäre die "maximale" Anzahl an Operationen, die O angibt, nicht die Minimale. --Bodo Thiesen 08:16, 17. Dez 2004 (CET)