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

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

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

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

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

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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$

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 01.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 31.01.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .

@Arthas018 0 / 0 / 0 Регистрация: 19.01.2017 Сообщений: 10

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

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

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

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

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

@Arthas018 0 / 0 / 0 Регистрация: 19.01.2017 Сообщений: 10
	28.01.2017, 16:44 [ТС]
	Спасибо большое, но вот насчет примера 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
	Arthas018, $https://www.cyberforum.ru/cgi-bin/latex.cgi?T(n)=T(n-1-k)+T(k)+C_1, T(1)=C_0$ 1