Алгоритми та структури даних · Middle · Запитання 64 з 75
Яка складність цієї функції?
function f(n) {
if (n <= 1) return 1;
return f(n / 2) + f(n / 2);
}- 1O(log n)
- 2O(n log n)
- ✓Правильна відповідь: O(n)
Пояснення
Кожен виклик робить два виклики на половині даних, тож дерево викликів має 1 + 2 + 4 + ... + n ≈ 2n вузлів по O(1) роботи. Якби виклик був один, лише f(n / 2), було б O(log n).