временная сложность рекурсивной функции первого шага графа

Question

Я начинающий в изучении рекурсивных функций и сложности во времени.У меня есть эта рекурсивная функция:

def walk(g, visited_Set):
    if g is None or g in visited: return
    visited_Set.add(g) ### mark as visited
    print(g.value) ### process before visiting outgoing edges
    for node in g.edges:
        walk(node, visited_Set) ### walk all outgoing edge targets

В худшем случае, если каждый узел подключен к другим узлам.Будет ли это ^ n временная сложность или n ^ 2 временная сложность?

Answer 1

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

Так что, если вы считаете, полный график на ваш худший случай, он имеет n(n-1)/2 ребер, что усложнит временную сложность O(n + n(n-1)/2) - O(n²).

Answer 2

Если в худшем случае каждый узел попадает на каждый другой узел, чем должно быть n ^ 2.

для каждого n (n раз), мы будем нажимать каждый раз n (n раз).Поэтому мы нажмем n, n раз.

Представьте, что у вас есть массив из 5 элементов:

[A, B, C, D, E]

, есликаждый индекс сравнивается с любым другим имеющимся у нас индексом:

A по сравнению с A, B, C, D, E (5 раз)

B по сравнению с A, B, C .... (5 раз)

...

E по сравнению с A, B, C, D, E (5 раз)

, если n = 5, чем у нас есть n^ 2: D