Landau-Symbole | Landau Notation - Was bedeutet O(n²) für einen Sortieralgorithmus

Question

Frage ist bereits oben angegeben.

Ich bin mir nicht ganz sicher wofür genau das O(n²) steht. Die Funktion wächst eben Quadratisch.

Was sagt mir das aber über den Sortieralgorithmus aus.

Im Vergleich, wenn ein Sortieralgorithmus linear wächst, also O(n).

Ist der O(n²) schneller als der O(n)?

Answer 1

Aloha :)

Bei einem Sortieralgorithmus misst die $O$-Notation im Prinzip, wie viele Vergleiche zwischen je 2 Elementen nötig sind. Wenn du z.B. 100 Zahlen sortiern willst, benötigt ein $O(n)$-Algorithmus etwa $n=100$ Vergleiche, ein $O(n^2)$-Algorithmus jedoch etwa um die $n^2=10.000$ Vergleiche. Ein $O(n)$-Algorithmus ist also erheblich schneller als ein $O(n^2)$-Algorithmus.