Algorithmen und Datenstrukturen · Senior · Frage 69 von 75
Welcher Ansatz zählt Inversionen (Paare i < j mit a[i] > a[j]) in O(n log n)?
- 1Counting Sort, gefolgt von einem einzigen linearen Durchlauf
- 2Zwei verschachtelte Schleifen mit frühem Abbruch, wenn sortiert
- 3Merge Sort, das linke Elemente zählt, die ein rechtes überholt
Antwort zeigen
Richtige Antwort: Merge Sort, das linke Elemente zählt, die ein rechtes überholt
Erklärung
Wird ein Element der rechten Hälfte vor den restlichen linken Elementen eingefügt, bildet es mit jedem davon eine Inversion. Ein Fenwick-Baum über die Werte funktioniert ebenfalls in O(n log n).