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.