Algorithmen und Datenstrukturen · Senior · Frage 63 von 75
Welche Komplexität hat Array.prototype.sort in V8 bei einem bereits sortierten Array?
- 1Etwa O(n)
- 2O(n log n) ohne Abkürzung
- 3O(n²)
Antwort zeigen
Richtige Antwort: Etwa O(n)
Erklärung
Timsort erkennt, dass das ganze Array ein aufsteigender Abschnitt ist, und macht nur eine lineare Prüfung. Das ist ein Grund, das eingebaute Sortieren einem handgeschriebenen Quicksort vorzuziehen.