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

@LuckyTheGreat · Регистрация: 22.03.2011

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

Чем будет являться сложность для нерекурсивного поиска с возвратом?

Полиномиальная не подходит, т.к. это всё-таки перебор в худшем случае.
Экспоненциальная тоже, т.к. в лучшем случае программа может найти решение с первой попытки.

Мне сказали, что это сумма всех возможных сложностей. Но как это?

Вот код, если нужно:

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
bool gamilton(int start)
{
int cur = start;
int next = 0;
path[next++] = cur;
bool found;
while (true)
{
found = false;
c[cur] = true;
for (int i = r[cur] + 1; i < n; i++)
if (i != cur && ((a[i,cur] == 1) || (a[cur,i] == 1)) && !c[i])
{
found = true;
r[cur] = i;
cur = i;
path[next++] = cur;
break;
}
if (!found)
{
if (next == 1) return false;
r[cur] = -1;
c[cur] = false;
cur = path[--next - 1];
}
else
if (next == n &&( (a[cur,start] == 1) || (a[start,cur] == 1))) return true;
}
}

@kolorotur · 04.12.2011, 16:00

Сложность алгоритма измеряется через разные нотации: омикрон (худший случай), омега (оптимальный случай), фита (средний случай).
Последней нотацией пользуются, как правило, когда омикрон и омега выдают одинаковое значение сложности алгоритма.

Видать, от вас просят вычислить сложность по каждой из нотаций и сложить их вместе.

@LuckyTheGreat · 04.12.2011, 21:20 **[ТС]**

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

Сложность алгоритма измеряется через разные нотации: омикрон (худший случай), омега (оптимальный случай), фита (средний случай).
Последней нотацией пользуются, как правило, когда омикрон и омега выдают одинаковое значение сложности алгоритма.

Видать, от вас просят вычислить сложность по каждой из нотаций и сложить их вместе.

Видимо. Но что из этого получится?

Новые блоги и статьи Все статьи Все блоги /
Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .	SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .	Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .
Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .	Lazarus. Таблица с объединением ячеек. Massaraksh7 21.03.2025 Понадобилась представление на экране таблицы с объединёнными ячейками. И не одной, а штук триста, и все разные. На Delphi я использовал для этих целей TStringGrid, и то, кривовато получалось. А в. . .	Async/await в Swift: Асинхронное программирование в iOS mobDevWorks 20.03.2025 Асинхронное программирование долго было одной из самых сложных задач для разработчиков iOS. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .	Колмогоровская сложность: Приёмы упрощения кода ArchitectMsa 20.03.2025 Наверное, каждый программист хотя бы раз сталкивался с кодом, который напоминает запутанный лабиринт — чем дальше в него погружаешься, тем сложнее найти выход. И когда мы говорим о сложности кода, мы. . .

@kolorotur 17810 / 12961 / 3381 Регистрация: 17.09.2011 Сообщений: 21,250
	04.12.2011, 16:00
	Сложность алгоритма измеряется через разные нотации: омикрон (худший случай), омега (оптимальный случай), фита (средний случай). Последней нотацией пользуются, как правило, когда омикрон и омега выдают одинаковое значение сложности алгоритма. Видать, от вас просят вычислить сложность по каждой из нотаций и сложить их вместе. 0

@LuckyTheGreat 18 / 18 / 11 Регистрация: 22.03.2011 Сообщений: 194
	04.12.2011, 21:20 [ТС]
	Сообщение от kolorotur Сложность алгоритма измеряется через разные нотации: омикрон (худший случай), омега (оптимальный случай), фита (средний случай). Последней нотацией пользуются, как правило, когда омикрон и омега выдают одинаковое значение сложности алгоритма. Видать, от вас просят вычислить сложность по каждой из нотаций и сложить их вместе. Видимо. Но что из этого получится? 0

Опции темы