0 / 0 / 0
Регистрация: 19.01.2017
Сообщений: 10
|
|
1 | |
Оценка сложности программы27.01.2017, 21:26. Показов 2620. Ответов 9
Метки нет (Все метки)
Очень нужно понять как найти функцию сложности рекурсии, но на разных сайтах так и не нашел понятных примеров. Если не сложно помогите с этим желательно на каком-нибудь примере.
0
|
27.01.2017, 21:26 | |
Ответы с готовыми решениями:
9
Оценка сложности алгоритма Теоретическая оценка сложности алгоритма Оценка вычислительной сложности алгоритма Считывание одномерного массива из файла. Оценка о-сложности алгоритма |
0 / 0 / 0
Регистрация: 19.01.2017
Сообщений: 10
|
||||||
27.01.2017, 21:45 [ТС] | 2 | |||||
Помогите пожалуйста!!! Никак не могу найти на разных сайтах тему с хорошими примерами про оценку сложности рекурсий.
Если не сложно объясните на каком-нибудь легком примере. А вообще нужно найти функцию сложности вот этой процедуры. Тут проверяется вырожденность дерева, код писал сам, поэтому он вряд ли сильно оптимизирован и т.д.
0
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
|
27.01.2017, 21:49 | 3 |
Arthas018, приведите конкретную функцию.
0
|
0 / 0 / 0
Регистрация: 19.01.2017
Сообщений: 10
|
||||||
27.01.2017, 22:06 [ТС] | 4 | |||||
Ну вот я написал процедуру проверки дерева на вырожденность
0
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
|
28.01.2017, 10:42 | 6 |
Arthas018, ну тут и без какого-либо анализа понятно, что для определения, является ли дерево вырожденное, вам в худшем случае (когда дерево вырожденное) надо пройтись по всем вершинам. Сложность — O(N).
Добавлено через 12 часов 27 минут Точнее O(h), где h - высота дерева.
0
|
0 / 0 / 0
Регистрация: 19.01.2017
Сообщений: 10
|
|
28.01.2017, 12:07 [ТС] | 7 |
Честно, сам я в этом плохо разбираюсь, но суть в том что нужно оценить сложность т.е. что-то вроде O(N).
И написать к ней функцию сложности, например, T(n)=5n+3. Просто сам я в этом не разбираюсь и думал что здесь помогут
0
|
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
|
|
28.01.2017, 15:04 | 8 |
Оценка сложности алгоритма показывает как возрастет время работы алгоритма, если поднять нагрузку с большой на очень большую. То есть, не важно сколько конкретно времени работает алгоритм. Важно показать что если n увеличить с 100500 до 201000, то тормоза возрастут в два раза. Поэтому и +3, и 5* из итоговой формулы выкидываются. Первое потому что при n=100500 роли не играет, второе потому что не влияет на факт "тормоза вырастут в два раза".
Конкретно в вашем примере на глазок линейное время. Потому что процедура вызывается один раз для каждого узла, итого число вызовов прямо пропорционально числу узлов.
1
|
0 / 0 / 0
Регистрация: 19.01.2017
Сообщений: 10
|
|
28.01.2017, 16:44 [ТС] | 9 |
Спасибо большое, но вот насчет примера T(n)= 5n+3. Это же и есть функция сложности, а O(T(n)) и получается простым O(n), т.е. линейная сложность на основе функции сложности. Но мне для задания желательно указать именно эту самую T(n) для примеров работы процедуры при минимальном, максимальном и тривиальном случаях.
0
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
|
28.01.2017, 17:27 | 10 |
Arthas018,
1
|
28.01.2017, 17:27 | |
28.01.2017, 17:27 | |
Помогаю со студенческими работами здесь
10
Сложности с написанием кода программы Сложности с написанием программы сопровождения базы данных Оценка сложности алгоритма Оценка сложности Flash Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |