Биг-О / Биг-О Нотация

Question

Я пытаюсь вычислить Big-O по следующему алгоритму, но я в замешательстве и мне нужна помощь:

Algorithm 1. DFS(G,n)
Input: G- the graph
       n- the current node
1) Visit(n)
2) Mark(n)
3) For every edge nm (from n to m) in G do
4)     If m is not marked then
5)         Dfs(G,m)
6)     End If
7) End For
Output: Depends on the purpose of the search...

Я даже не стану говорить, что я (неправильно) вычислил решениебыть.Кто-нибудь может помочь мне и объяснить это мне?

Спасибо.

РЕДАКТИРОВАТЬ: Очевидно, мой расчет O(n+m) является правильным ... может кто-нибудь проверить это?

РЕДАКТИРОВАТЬ 2: Или это O(|n|+|m|)?

Answer 1

Его стоимость равна O (n + e), где n - количество узлов, а e - количество ребер.

Answer 2

Позволяет интегрировать все узлы в G

• строка 1 и строка 2 вызывается один раз для каждого узла в G;т. е. O (N), где N - количество узлов
• , строки 4 вызываются один раз для каждого ребра в G;то есть O (E), где E - число ребер.
• строка 5 вызывается один раз для каждого узла в G (за исключением узла, с которого мы начали);то есть O (N).

Это делает вычисление O(N + E), которое может быть уменьшено до O(E) с E >= N.

Это предполагает, что мы просто считаем шаги равными.На практике мы не знаем относительную стоимость различных шагов.Когда они подключены, сложность может быть другой.

Answer 3

Это похоже на простую DFS на графике, попробуйте сделать несколько простых примеров алгоритма, выясните, сколько итераций вам нужно сделать, и посмотрите, как это соотносится с вашими входными значениями (n числом узлов и mколичество ребер)