Исчерпывающий поиск Big-O

Question

В данный момент я работаю над некоторой ревизией и специально перебираю нотацию Big-O. Я задал похожий вопрос (который имел дело с другим алгоритмом), но все еще не уверен, правильно ли я поступаю или нет.

Алгоритм, на который я смотрю, - это исчерпывающий поиск (он же, я думаю, грубая сила), который выглядит так:

Input: G- the graph
   n- the current node
   p– the path so far
1) For every edge nm (from n to m) in G do
2)    If m ∉ p then
3)       p = p ∪ {m}
4)       Exhaustive(G, m, p)
5)    End If
6) End For

До сих пор я пришел к выводу, что этот алгоритм O(n) - это правильно? Я сомневаюсь, что это так, и хотел бы точно знать, как это сделать; что искать, что именно я «подсчитываю» каждый раз и т. д. Я понимаю, что необходимо подсчитать количество выполняемых операций, но это все, что мне нужно принять к сведению / count?

РЕДАКТИРОВАТЬ: я узнал, что этот алгоритм, на самом деле, O((n-1)!) - это правильно, и если так, как это решение возникло, когда я не могу его решить?

Answer 1

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

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

Чтобы увидеть, что наихудший вариант выполнения - O((n-1)!), подумайте, сколько путей в полностью связанном графе - вы можете посетить любой узел непосредственно с любого узла.Другой способ сформулировать это так: вы можете посещать узлы в любом порядке, сохраняя начальное состояние.Это то же самое, что и число перестановок (n-1) элементов.Я полагаю, что на самом деле это будет O(n!), так как мы перебираем все ребра, что занимает O(n) для каждого состояния на пути (n*(n-1)!). РЕДАКТИРОВАТЬ : Точнее, мы можем сказать, что это big-omega(N!).Смотрите комментарии для более подробной информации.

Иногда проще взглянуть на то, что алгоритм вычисляет, чем на реальный код - то есть на количество элементов всех состояний (здесь более детально, пути).