Оценка сложности программы

@Arthas018 · Регистрация: 19.01.2017

Author24 — интернет-сервис помощи студентам

Очень нужно понять как найти функцию сложности рекурсии, но на разных сайтах так и не нашел понятных примеров. Если не сложно помогите с этим желательно на каком-нибудь примере.

@Arthas018 · 27.01.2017, 21:45 **[ТС]**

Помогите пожалуйста!!! Никак не могу найти на разных сайтах тему с хорошими примерами про оценку сложности рекурсий.
Если не сложно объясните на каком-нибудь легком примере. А вообще нужно найти функцию сложности вот этой процедуры.

Тут проверяется вырожденность дерева, код писал сам, поэтому он вряд ли сильно оптимизирован и т.д.

C++

void V_tree(Node *&tree, int &kol, bool &quit) // Процедура проверки на вырожденность
{
    kol += 2;
    if (NULL == *&tree)// Если пустое
    {
        kol ++;
        quit = true;
        return;
    }
    else // Иначе проверяем поддеревья
    {
        kol += 4;
        if ((tree->l != NULL) && (tree->r != NULL))// Если оба непустые
        {
            kol++;
            quit = false;
            return;
        }
        kol += 3;
        if ((tree->l == NULL) && (tree->r != NULL))// Проверяем правое
        {
            V_tree(tree->r, kol,quit);
        }
        kol += 3;
        if ((tree->l != NULL) && (tree->r == NULL))// Проверяем левое
        {           
            V_tree(tree->l, kol,quit);
        }
        kol += 5;
        if ((NULL != *&tree) && (tree->l == NULL) && (tree->r == NULL)) // Последний элемент
        {
            kol++;
            quit = true;
            return;
        }
    }
}

@HenryDukart · 27.01.2017, 21:49

Arthas018, приведите конкретную функцию.

@Arthas018 · 27.01.2017, 22:06 **[ТС]**

Ну вот я написал процедуру проверки дерева на вырожденность

C++

void V_tree(Node *&tree, int &kol, bool &quit) // Процедура проверки на вырожденность
{
    kol += 2;
    if (NULL == *&tree)// Если пустое
    {
        kol ++;
        quit = true;
        return;
    }
    else // Иначе проверяем поддеревья
    {
        kol += 4;
        if ((tree->l != NULL) && (tree->r != NULL))// Если оба непустые
        {
            kol++;
            quit = false;
            return;
        }
        kol += 3;
        if ((tree->l == NULL) && (tree->r != NULL))// Проверяем правое
        {
            V_tree(tree->r, kol,quit);
        }
        kol += 3;
        if ((tree->l != NULL) && (tree->r == NULL))// Проверяем левое
        {           
            V_tree(tree->l, kol,quit);
        }
        kol += 5;
        if ((NULL != *&tree) && (tree->l == NULL) && (tree->r == NULL)) // Последний элемент
        {
            kol++;
            quit = true;
            return;
        }
    }
}

но пример можно привести и на любой другой( например поиск чисел Фибоначчи)

@The535 · 27.01.2017, 23:00

Тык
Что подразумевается под оценкой сложности программы? Качество кода? Скорость работы? Память? Вопрос не корректный.
А сложность рекурсии это что? Сложность понимания? Глубина?

@HenryDukart · 28.01.2017, 10:42

Arthas018, ну тут и без какого-либо анализа понятно, что для определения, является ли дерево вырожденное, вам в худшем случае (когда дерево вырожденное) надо пройтись по всем вершинам. Сложность — O(N).

Добавлено через 12 часов 27 минут
Точнее O(h), где h - высота дерева.

@Arthas018 · 28.01.2017, 12:07 **[ТС]**

Честно, сам я в этом плохо разбираюсь, но суть в том что нужно оценить сложность т.е. что-то вроде O(N).
И написать к ней функцию сложности, например, T(n)=5n+3. Просто сам я в этом не разбираюсь и думал что здесь помогут

@Renji · 28.01.2017, 15:04

Сообщение от Arthas018

T(n)=5n+3

Оценка сложности алгоритма показывает как возрастет время работы алгоритма, если поднять нагрузку с большой на очень большую. То есть, не важно сколько конкретно времени работает алгоритм. Важно показать что если n увеличить с 100500 до 201000, то тормоза возрастут в два раза. Поэтому и +3, и 5* из итоговой формулы выкидываются. Первое потому что при n=100500 роли не играет, второе потому что не влияет на факт "тормоза вырастут в два раза".

Конкретно в вашем примере на глазок линейное время. Потому что процедура вызывается один раз для каждого узла, итого число вызовов прямо пропорционально числу узлов.

@Arthas018 · 28.01.2017, 16:44 **[ТС]**

Спасибо большое, но вот насчет примера T(n)= 5n+3. Это же и есть функция сложности, а O(T(n)) и получается простым O(n), т.е. линейная сложность на основе функции сложности. Но мне для задания желательно указать именно эту самую T(n) для примеров работы процедуры при минимальном, максимальном и тривиальном случаях.

@HenryDukart · 28.01.2017, 17:27

Arthas018,

$https://www.cyberforum.ru/cgi-bin/latex.cgi?T(n)=T(n-1-k)+T(k)+C_1, T(1)=C_0$

@Arthas018 0 / 0 / 0 Регистрация: 19.01.2017 Сообщений: 10
		1
	Оценка сложности программы 27.01.2017, 21:26. Показов 2620. Ответов 9 Метки нет (Все метки) Очень нужно понять как найти функцию сложности рекурсии, но на разных сайтах так и не нашел понятных примеров. Если не сложно помогите с этим желательно на каком-нибудь примере. 0

@HenryDukart 125 / 125 / 44 Регистрация: 05.10.2013 Сообщений: 462
	27.01.2017, 21:49	3
	Arthas018, приведите конкретную функцию. 0

@The535 26 / 26 / 18 Регистрация: 16.01.2014 Сообщений: 161
	27.01.2017, 23:00	5
	Тык Что подразумевается под оценкой сложности программы? Качество кода? Скорость работы? Память? Вопрос не корректный. А сложность рекурсии это что? Сложность понимания? Глубина? 0

@HenryDukart 125 / 125 / 44 Регистрация: 05.10.2013 Сообщений: 462
	28.01.2017, 10:42	6
	Arthas018, ну тут и без какого-либо анализа понятно, что для определения, является ли дерево вырожденное, вам в худшем случае (когда дерево вырожденное) надо пройтись по всем вершинам. Сложность — O(N). Добавлено через 12 часов 27 минут Точнее O(h), где h - высота дерева. 0

@Arthas018 0 / 0 / 0 Регистрация: 19.01.2017 Сообщений: 10
	28.01.2017, 12:07 [ТС]	7
	Честно, сам я в этом плохо разбираюсь, но суть в том что нужно оценить сложность т.е. что-то вроде O(N). И написать к ней функцию сложности, например, T(n)=5n+3. Просто сам я в этом не разбираюсь и думал что здесь помогут 0

@Renji 2782 / 1935 / 570 Регистрация: 05.06.2014 Сообщений: 5,600
	28.01.2017, 15:04	8
	Сообщение от Arthas018 T(n)=5n+3 Оценка сложности алгоритма показывает как возрастет время работы алгоритма, если поднять нагрузку с большой на очень большую. То есть, не важно сколько конкретно времени работает алгоритм. Важно показать что если n увеличить с 100500 до 201000, то тормоза возрастут в два раза. Поэтому и +3, и 5* из итоговой формулы выкидываются. Первое потому что при n=100500 роли не играет, второе потому что не влияет на факт "тормоза вырастут в два раза". Конкретно в вашем примере на глазок линейное время. Потому что процедура вызывается один раз для каждого узла, итого число вызовов прямо пропорционально числу узлов. 1

@Arthas018 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

@HenryDukart 125 / 125 / 44 Регистрация: 05.10.2013 Сообщений: 462
	28.01.2017, 17:27	10
	Arthas018, $https://www.cyberforum.ru/cgi-bin/latex.cgi?T(n)=T(n-1-k)+T(k)+C_1, T(1)=C_0$ 1

Опции темы