Выбор ответа Middle Сложность спрашивают часто обновлено
Наивная рекурсия Фибоначчи
Вопрос
Какая сложность по времени у наивного рекурсивного fib(n)?
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(2ⁿ). Каждый вызов порождает два новых, глубина дерева n: число вызовов растёт экспоненциально, верхняя оценка O(2ⁿ) (точнее около O(1.618ⁿ), но на собесе ждут O(2ⁿ)). - O(n): так станет с мемоизацией или циклом. - O(n²) и O(n log n):…
Варианты ответа
- O(n)
- O(2ⁿ)правильный ответ
- O(n²)
- O(n log n)
Разбор
Каждый вызов порождает два новых, глубина дерева n: число вызовов растёт экспоненциально, верхняя оценка O(2ⁿ) (точнее около O(1.618ⁿ), но на собесе ждут O(2ⁿ)).
- O(n): так станет с мемоизацией или циклом.
- O(n²) и O(n log n): полиномиальные оценки сильно занижают число повторных вычислений.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.