welcher Algorithmus ist schneller?
Die Laufzeitkomplexität von Algorithmus A liegt in O(n2 ), die von Algorithmus B in O(n log n). Welcher ist schneller ?
4 Antworten
Ich habe mich beim ersten Lesen auch hinreißen lassen. Danke an Jangler13 für die Korrektur.
Zwar hängen die beiden Klassen insoweit zusammen als dass
gilt, aber das sagt natürlich nichts darüber aus, welcher Algorithmus schneller ist.
Es könnte
sein, dann wäre B schneller als A. Andererseits können
sein, dann wäre A schneller als B.
Die Landau-Notation bedeutet anschaulich "wächst höchstens so schnell wie". Das heißt, die Laufzeiten von A und B haben zwar verschiedene obere Schranken, das sagt aber trotzdem nichts darüber aus, wie sie innerhalb der Laufzeitkomplexität "angeordnet" sind. Gut möglich, dass n² eine "Luxus-Schranke" für A und es eigentlich noch eine viel kleinere Klasse gäbe, in der A enthalten ist.
Du hast natürlich völlig Recht, da hatte ich die falsche Beschränktheit im Sinn. Danke für die Korrektur, ich habe meine Antwort angepasst.
Das kann man so nicht beurteilen, da die O Notation nur beschreibt, wie die Laufzeit sich verhält, wenn n immer größer wird.
Das f in O(g) liegt, bedeutet per Definition, dass Lim sup n->unendlich |f(n)/g(n)| kleiner als unendlich ist.
Da n größer ist, als Log(n) für n groß genug, gilt n*log(n) liegt in O(n^2)
Es kann also sein, dass A auch in O(n*log(n)) liegt. (Die Groß Theta Notation würde dies nicht erlauben)
Die Groß O Notation besagt nur, was von dem beiden schneller anwächst, nicht was davon tatsächlich schneller ist.
Beispiel:
Die Laufzeit von A ist 1000000*n, die Laufzeit von B ist n^2, somit ist A offensichtlich in Theta(n) und b ist in Theta(n^2), B wächst also Asymptotisch schneller als A, jedoch ist der Algorithmus B für n kleiner als 1000 schneller.
Beispiel 2:
A hat die Laufzeit n, B hat die Laufzeit n^2, es gilt, dass A in O(n^3) liegt, und B in O(n^4)
n^4 wächst Asymptotisch Schneller als n^3, trotzdem wächst n^2 Asymptotisch Schneller als n.
Wie du siehst sagt die Groß O Notation nicht aus, welche der beiden Algorithmen Asymptotisch besser ist, es ist eher dazu da, damit man eine Obere Schranke für die Laufzeit hat, mit der man die Laufzeit nach oben Einschränken kann.
Im schlechtesten Fall ist natürlich O(n log n) schneller, denn nlog(n) < n^2 für alle n > 1.
D.h. die Schranke für O(nlog(n)) liegt weiter unten.
O(log n) <= O(n) <= O(n log n) <= O( n^2 ) - wobei <= hier ein Untermengenzeichen sein sollte.
Muss nicht unbedingt stimmen, wenn A in Theta(1) und B in Theta(n) liegt, gilt ja trotzdem die obige Eigenschaft, B ist aber langsamer als A (für n groß genug)