Форум программистов, компьютерный форум CyberForum.ru

Временная оценка алгоритма - C++

Восстановить пароль Регистрация
 
Garred
 Аватар для Garred
279 / 77 / 4
Регистрация: 19.04.2011
Сообщений: 217
07.12.2011, 20:59     Временная оценка алгоритма #1
Уважаемые форумчане, помогите сделать временную оценку выполнения рекурсивных алгоритмов (или хотя бы одного). Мне не нужна программная реализация этого, а именно теоретические вычисления вручную. Желательно с п объяснениями. Буду очень благодарен.

C++
1
2
3
4
5
6
int fac(int n)
{
   if (n==0) return 1;
   n=n*fac(n-1);  
   return n;
}
C++
1
2
3
4
5
size_t fib(size_t n)
{
    if(n==0||n==1) return 1;
    return fib(n-1)+fib(n-2);
}
Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2011, 20:59     Временная оценка алгоритма
Посмотрите здесь:

Временная сложность алгоритма C++
C++ Оценка алгоритма
временная остановка)))) C++
Считывание одномерного массива из файла. Оценка о-сложности алгоритма C++
Список учеников имеет следующую структуру: фамилия – класс - оценка по алгебре - оценка по физике - средний балл C++
Какова временная сложность метода ветвей и границ, и генетического алгоритма, которые решают задачу о рюкзаке? C++
Оценка вычислительной сложности алгоритма C++
C++ Временная сложность алгоритма

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
08.12.2011, 10:07     Временная оценка алгоритма #2
Приблизительная асимптотическая сложность.
1. f(n) = O(n) -- количество операций строго пропорционально входящим данным.
2. f(n) = O(2 ^ n) -- каждый вызов порождает еще два вызова, количество операций пропорционально 2 ^ n.

Из-за ограничений текстового сообщения:
Вместо знака равенства должен быть знак принадлежности.
Вместо символа O (ограничение сверху), должен быть символ theta (ограничение сверху и снизу).
Yandex
Объявления
08.12.2011, 10:07     Временная оценка алгоритма
Ответ Создать тему
Опции темы

Текущее время: 11:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru