Временная сложность DFS в линейном времени

Question

Я перепутал со сложностью по времени приведенного ниже алгоритма, это O (V) или O (V + E)?

DFS(G,s,t):


vis[s] = true
        if s == t
            vis[s] = false, return 1
        cont = 0
        for v is adj(s)
            if vis[v] == false
                cont = cont + DFS(G,s,t)
        vis[s] = false
        return cont

Answer 1

При изучении теории сложности графов иногда проще подумать, «сколько раз я обрабатываю каждое ребро / вершину», сколько раз этот цикл выполняется.Это потому, что циклы в графах имеют переменную длину, а с повторениями все становится беспорядочно.

В конечном счете, в алгоритме DFS вам нужно будет проверить, что находится на другом конце каждого ребра, и решить, посещать ли вершину или нет.Вы будете делать это ровно один раз и только один раз для каждого края.Итак, вы обязаны рассмотреть каждое ребро.

Поскольку каждая вершина также рассматривается (посещается) ровно один раз, то это приводит к сложности O (V + E).