Zitat von
Alexander:
ich habe schon öfter Komplexitätsangaben von veschiedenen (Sortier-) Algorithmen gesehen.
Mich würde mal interessieren, wie man die abschätzen kann, ohne groß zu rechnen und Messungen durchzuführen. Es soll dann natürlich nur eine ungefähre Angabe sein.
Bei den Sortieralgorithmen gibt es ja im Prinzip zwei Gruppen, die mit einer logarithmischen und einer quadratischen Komplexität.
Es gibt mehr "Gruppen":
Code:
linear: O(N)=N
logarithmisch: O(N)=N*Log(N)
quadratisch: O(N)=N*N
kubisch(*): O(N)=N^3
potenziert(*): O(N)=2^N
fakultät(*): O(N)=N!
die Bezeichnungen mit dem * habe ich erfunden.
In der
O-Schreibweise bezeichnet das Argument N die Anzahl der Eingangsdaten und O(N) ist
annähernd proportional der Laufzeit.
Man kann jetzt nicht behaupten, dass ein quadratischer Algo schneller als ein logarithmischer ist,
aber bei grossen Werten von N wird der logarithmische besser abschneiden.