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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Garred
 Аватар для Garred
282 / 80 / 4
Регистрация: 19.04.2011
Сообщений: 218
#1

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

07.12.2011, 20:59. Просмотров 940. Ответов 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++
Оценка вычислительной сложности алгоритма C++
C++ Временная сложность алгоритма
C++ Оценка сложности алгоритма
Теоретическая оценка сложности алгоритма C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2915 / 1344 / 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     Временная оценка алгоритма
Ответ Создать тему
Опции темы

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