Алгоритми та структури даних · Senior · Запитання 69 з 75
Який підхід рахує інверсії (пари i < j з a[i] > a[j]) за O(n log n)?
- 1Сортування підрахунком і один лінійний прохід
- 2Два вкладені цикли з раннім виходом, коли все відсортовано
- ✓Правильна відповідь: Сортування злиттям із підрахунком лівих елементів, які обганяє кожен правий
Пояснення
Коли елемент правої половини зливається раніше за решту лівих, він утворює інверсію з кожним із них. Дерево Фенвіка по значеннях теж працює за O(n log n).