Как расчитать сложность алгоритма
В курсаче есть задание: сделать алгоритм нахождения всех контуров в орграфе и расчитать его теоретическую сложность. Алгоритм я сделал на основе дерева списка, а вот как быть с его теоретической сложностью? Дайте, по-ста, "вектор направления" или какие-то наставления.
Время работы алгоритма в зависимости от кол-ва элементов
Время не совсем корректный термин по скольку по описанию алгоритма математически его обосновать не получится. Скорее количество операций в зависимости от количества элементов. Причем интересует не столько точное количество операций, а O большое от этого количества, поскольку его проще оценить. Какой вектор движения может быть - собственно автор ты же писал алгоритм, ты должен оценить какие шаги алгоритма зависят от размера данных и что это за зависимость. Ну или выкладывай алгоритм сюда - рассмотрим на примере.
Пусть A-матрица смежности, B-матрица достижимости.
1)С помощью матрицы достижимости строим ордерево с корнем в рассматриваемой вершине если A[k]*B[k]=1, то добавляем i-ую вершину, пока i<=Max. Затем для каждого i вызываем рекурсивно ту же операцию.
2)Если i==k, то контур с меткой k найден
3)Исключаем из A и B столбцы и строки
с номером k
Пока A и B повторяем описанные выше три действия
Поясняющий рисунок:
k
/ | \
i i i
/ \ | \
j j j k<---контур, проходящий вершины k-i
/
k <---- контур, проходящий вершины k-i-j
Выше нарисовано ордерево: допустим какой-то вершине присвоем метку k, тогда ищем все контура, проходящие через эту вершину. Когда нашли, тогда исключаем вершину k, и продолжаем поиск опять пока все контуры не найдены.
P.S.: Пытался изобразить дерево, но не получилось. Думаю вы разберетесь, если представите, что буквы это листья, а слеши - ветки
1)С помощью матрицы достижимости строим ордерево с корнем в рассматриваемой вершине если A[k]*B[k]=1, то добавляем i-ую вершину, пока i<=Max. Затем для каждого i вызываем рекурсивно ту же операцию.
2)Если i==k, то контур с меткой k найден
3)Исключаем из A и B столбцы и строки
с номером k
Пока A и B повторяем описанные выше три действия
Поясняющий рисунок:
k
/ | \
i i i
/ \ | \
j j j k<---контур, проходящий вершины k-i
/
k <---- контур, проходящий вершины k-i-j
Выше нарисовано ордерево: допустим какой-то вершине присвоем метку k, тогда ищем все контура, проходящие через эту вершину. Когда нашли, тогда исключаем вершину k, и продолжаем поиск опять пока все контуры не найдены.
P.S.: Пытался изобразить дерево, но не получилось. Думаю вы разберетесь, если представите, что буквы это листья, а слеши - ветки