Algorithmen und Datenstrukturen · Senior · Frage 30 von 75
Warum kann ein O(n log n)-Algorithmus auf echten Eingaben gegen einen O(n²)-Algorithmus verlieren?
- 1Die O-Notation verbirgt Konstanten, und bei kleinem n dominieren sie
- 2O(n²)-Algorithmen werden mit mehr Optimierungen kompiliert
- 3O(n log n) gilt nur, wenn n eine Zweierpotenz ist
Antwort zeigen
Richtige Antwort: Die O-Notation verbirgt Konstanten, und bei kleinem n dominieren sie
Erklärung
Insertion Sort schlägt Merge Sort unter ein paar Dutzend Elementen dank winzigem Overhead und cachefreundlichem Zugriff. Deshalb wechseln Timsort und Introsort bei kurzen Abschnitten zu Insertion Sort.