Algorytmy i struktury danych · Middle · Pytanie 64 z 75
Jaka jest złożoność tej funkcji?
function f(n) {
if (n <= 1) return 1;
return f(n / 2) + f(n / 2);
}- 1O(log n)
- 2O(n log n)
- ✓Poprawna odpowiedź: O(n)
Wyjaśnienie
Każde wywołanie robi dwa wywołania na połowie danych, więc drzewo wywołań ma 1 + 2 + 4 + ... + n ≈ 2n węzłów po O(1) pracy. Gdyby wywołanie było jedno, samo f(n / 2), byłoby O(log n).