Algorytmy i struktury danych · Senior · Pytanie 23 z 75
Według twierdzenia o rekurencji uniwersalnej, jaka jest złożoność T(n) = 2T(n/2) + O(n)?
- 1O(n), jak jedna pętla
- 2O(n²) przez dwa wywołania
- ✓Poprawna odpowiedź: O(n log n)
Wyjaśnienie
Dwie połowy z liniową pracą na scalenie to rekurencja sortowania przez scalanie. Każdy z log n poziomów rekurencji wykonuje łącznie O(n) pracy. T(n) = 2T(n/2) + O(1) dałoby O(n), a T(n) = T(n/2) + O(1) to wyszukiwanie binarne, O(log n).