Algorytmy i struktury danych · Senior · Pytanie 69 z 75
Które podejście liczy inwersje (pary i < j z a[i] > a[j]) w O(n log n)?
- 1Sortowanie przez zliczanie i jedno liniowe przejście
- 2Dwie zagnieżdżone pętle z wczesnym wyjściem, gdy wszystko posortowane
- ✓Poprawna odpowiedź: Sortowanie przez scalanie, licząc lewe elementy, które wyprzedza każdy prawy
Wyjaśnienie
Gdy element z prawej połowy jest scalany przed pozostałymi lewymi, tworzy inwersję z każdym z nich. Drzewo Fenwicka po wartościach też działa w O(n log n).