Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Поиск вершины с максимальной степенью в двудольном графе http://www.cyberforum.ru/algorithms/thread2199201.html
Здравствуйте, имеется двудольный граф (X, Y). X - это пары целых чисел Y - это просто целые числа: k и смежно k <=> a <= k <= b Нужно найти вершину из Y с максимальной степенью (если их...
Алгоритмы Нужен пример программы для многоленточной машины Тьюринга Прошу поделиться программой для многоленточной машины Тьюринга. Например, двух-ленточная машина Тьюринга, даны два числа на исходной ленте. Сложить их и результат записать на другую ленту. Не... http://www.cyberforum.ru/algorithms/thread2199166.html
Алгоритмы Дробная часть троично-симметричной системы счисления
Всем привет! У меня возникла проблема. Мне нужен алгоритм перевода дробной части числа из десятичной системы счисления в троично-симметричную. Как переводит целые числа в интернете информации полным...
шахтеры Алгоритмы
добрый вечер! я очень люблю этот форум, классные ребята, неоднократно выручили меня очень быстро и квалифицировано, по этому для меня более весомые ихние советы и рекомендации чем на других форумах!...
Алгоритмы Быстрый поиск пар http://www.cyberforum.ru/algorithms/thread2193024.html
Здравствуйте. Задача такая: есть N прямоугольных "коробок" и N прямоугольных "вещей" (все они заданы парами ширина-высота, поворачивать нельзя), нужно для каждой вещи найти коробку, в которую она...
Алгоритмы Кольцевые списки Зачем нужны кольцевые односвязные и двусвязные списки? Когда они могут понадобиться? Ведь, если цель задачи - просто сделать циклический набор данных, можно то же самое решить массивом и операцией... подробнее
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
25.02.2018, 20:31 0

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

25.02.2018, 20:31. Просмотров 817. Ответов 3
Метки (Все метки)

Ответ

Цитата Сообщение от 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.02.2018, 20:31
Готовые ответы и решения:

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

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

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

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

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

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