Python для начинающих

Форум программистов и сисадминов Киберфорум

Войти

Регистрация
Восстановить пароль

Рейтинг 4.53/47:

4abrec

0 / 0 / 0

Регистрация: 20.05.2019

Сообщений: 1

Сложность рекурсивного алгоритма Фибоначчи

30.10.2019, 20:11. Показов 9698. Ответов 3

Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам

Есть алгоритм вычисления n-го числа фибоначчи через рекурсию, поясните пожалуйста почему его сложность 2^n

Python
1
2
3
4
def fib_rec(n):
    if n in (1,2):
        return 1
    return fib_rec(n-1) + fib_rec(n-2)

Programming

Эксперт

39485 / 9562 / 3019

Регистрация: 12.04.2006

Сообщений: 41,671

Блог

30.10.2019, 20:11

Ответы с готовыми решениями:

Временная сложность алгоритма с несколькими переменными
Здравствуйте, помогите пожалуйста разобраться, нигде не могу найти. Бывает ли сложность алгоритма от нескольких переменных? ...

Как оценить сложность алгоритма?
К примеру, есть один и второй код. Какая у них сложность? n = mylist = list(set(n)) print mylist i = 0 while i <...

Сложность рекурсивного алгоритма
Добрый день, никак не могу понять как высчитывать сложность алгоритмов с рекурсией. Буду очень благодарна если кто-нибудь поможет...

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	30.10.2019, 20:28
	https://stackoverflow.com/a/360773/10913399 1

Welemir1

Автоматизируй это!

7392 / 4819 / 1246

Регистрация: 30.03.2015

Сообщений: 13,694

Записей в блоге: 29

30.10.2019, 20:48

Сообщение от 4abrec

fib_rec(n-1) + fib_rec(n-2)

так вот же

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	31.10.2019, 11:15
	А вы вставьте print в каждый вызов, сразу всё станет ясно. 0

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

inter-admin

Эксперт

29715 / 6470 / 2152

Регистрация: 06.03.2009

Сообщений: 28,500

Блог

31.10.2019, 11:15

Помогаю со студенческими работами здесь

Сложность рекурсивного алгоритма
Здравствуйте, уважаемые форумчане! Помогите пожалуйста посчитать сложность такого рекурсивного алогоритма: function Process...

Сложность рекурсивного алгоритма - Алгоритмы
Добрый день, Никак не могу понять как высчитать сложность этого алгоритма с рекурсией(задача коммивояжёра). Буду очень благодарен...

Сложность алгоритма нахождения n-го числа Фибоначчи
Здравствуйте, делаю проект, в докладе которого мне нужно указать сложности используемых алгоритмов. Один из эти алгоритмов рекурсивный...

Определить временную сложность алгоритма (рекурсивная функция, числа Фибоначчи)
Код представлен на Паскале: function R (N: integer): integer; begin if N<= 1 then return (1) else return (R(N-1) +...

Как вычислять сложность алгоритма, или найти асимптотическую сложность любой программки?
Например Вычислить x^n по алгоритму быстрого возведения в степень Добавлено через 43 секунды var x, n, r: word; ...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

Наверх