Алгоритми та структури даних · Senior · Запитання 23 з 75
За основною теоремою, яка складність T(n) = 2T(n/2) + O(n)?
- 1O(n), як один цикл
- 2O(n²) через два виклики
- ✓Правильна відповідь: O(n log n)
Пояснення
Дві половини з лінійною роботою на об'єднання - це рекурентність сортування злиттям. Кожен із log n рівнів рекурсії разом виконує O(n) роботи. T(n) = 2T(n/2) + O(1) дало б O(n), а T(n) = T(n/2) + O(1) - це бінарний пошук, O(log n).