Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
WhiscasH
1 / 1 / 1
Регистрация: 06.03.2016
Сообщений: 60
1

Определить временную сложность алгоритма (рекурсивная функция, числа Фибоначчи)

25.02.2018, 15:35. Просмотров 805. Ответов 3

Код представлен на Паскале:

Pascal
1
2
3
4
5
6
function R (N: integer): integer;
begin
    if N<= 1 then return (1)
    else 
        return (R(N-1) + R(N-2))
end;
Не могу понять, как найти сложность такого алгоритма.
Что нужно сделать, чтобы ее найти?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.02.2018, 15:35
Ответы с готовыми решениями:

Как определить временную сложность алгоритма?
Никак не могу разобраться как считается временная сложность алгоритма :с const...

Теория алгоритмов. Определить О-сложность заданного алгоритма. Определить интервалы функционального доминирова
1. Определить О-сложность заданного алгоритма 2. Определить интервалы...

Определить сложность алгоритма методом моделирования
Здравствуйте. Есть задача определить сложность алогритма, заданного...

Задача на временную сложность
Помогите с задачей, не понимаю логики решения. Алгоритм выполняется за 0,5 мс...

Нужно определить сложность алгоритма по блок-схеме
Помогите пожалуйста.

3
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
25.02.2018, 16:10 2
Лучший ответ Сообщение было отмечено WhiscasH как решение

Решение

нужно понять, чему она равна. с ходу сложно это сделать. все, что у нас есть - это уравнение на нее. обозначим сложность вычисления R(n) за T(n). посмотрев на код, мы видим, что чтобы вычислить R(n) надо сначала вычислить R(n-1), затем R(n-2) и затем сложить их. получается, что T(n) = T(n-1) + T(n-2) + small_constant. мы составили рекурентное соотношение на T(n). у него есть база типа T(0) = T(1) = 1. короче говоря, получается, что число операций необходимых для вычисления T(n) примерно равно R(n).
1
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,426
25.02.2018, 19:41 3
Цитата Сообщение от salam Посмотреть сообщение
обозначим сложность вычисления R(n) за T(n)
Цитата Сообщение от salam Посмотреть сообщение
получается, что число операций необходимых для вычисления T(n) примерно равно R(n)
Что-то тут не так.
0
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
25.02.2018, 20:31 4
Цитата Сообщение от WhiscasH Посмотреть сообщение
Код представлен на Паскале:
Насколько я помню, в Паскале нет оператора return.

Цитата Сообщение от Shamil1 Посмотреть сообщение
Цитата Сообщение от salam Посмотреть сообщение
получается, что число операций необходимых для вычисления T(n) примерно равно R(n).
Что-то тут не так.
Запятых не хватает:
получается, что число операций, необходимых для вычисления, T(n) примерно равно R(n).

T(n)>R(n)

Кроме этого, T(n) < R(n) +Q(n)*small_constant, где Q(0)=Q(1)=1, Q(n)=Q(n-1)+Q(n-2)+1. По-видимому, ассимптота log Q(n) ~ n/2, Q(n)~(1,62)^n.

Поскольку R(n) также растёт экспоненциально, log T(n) = O(n).
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.02.2018, 20:31

Сложность алгоритма
Нужно определить сложность алгоритма. Я совсем не понял как это делается. ...

Сложность алгоритма
пусть имеется алгоритм f со сложностью О(n*log n). Если этот алгоритм...

Сложность алгоритма
Кто бы объяснил рабоче-крестьянским языком что такое O(N) ? И если есть...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru