深度优先搜索时间复杂度

Question

下面是深度搜索算法的代码。

def add_edge(adj, s, t):
    # Add edge from vertex s to t
    adj[s].append(t)
    # Due to undirected Graph
    adj[t].append(s)
    print('adj add edge', adj)


def dfs_rec(adj, visited, s, loop_count):
    # Mark the current vertex as visited
    visited[s] = True
    print(f'Visited vertex: {s}')

    # Recursively visit all adjacent vertices
    for i in adj[s]:
        loop_count[0] += 1  # Increment the loop counter
        if not visited[i]:
            dfs_rec(adj, visited, i, loop_count)


def dfs(adj, s):
    visited = [False] * len(adj)
    print('Initial visited list:', visited)

    # Create a list to hold loop count as a mutable object
    loop_count = [0]  # This will hold the number of times the loop runs

    # Start DFS recursion
    dfs_rec(adj, visited, s, loop_count)

    # Return the loop count
    return loop_count[0]


if __name__ == "__main__":
    V = 5

    # Create an adjacency list for the graph
    adj = [[] for _ in range(V)]

    # Define the edges of the graph
    edges = [[1, 2], [1, 0], [2, 0], [2, 3], [2, 4], [1, 3], [1, 4], [3, 4], [0, 3], [0, 4]]

    # Populate the adjacency list with edges
    for e in edges:
        print('Adding edge:', e)
        add_edge(adj, e[0], e[1])

    source = 1
    print(f"\nDFS traversal from source vertex: {source}")
    total_loops = dfs(adj, source)
    print(f"Total number of times the for loop ran: {total_loops}")

时间复杂度为O(V+E)。但如果我运行这段代码，我会得到以下输出：

for循环运行的总次数：20

即 O(edges=5)² 那么时间复杂度 O(V+E) 是多少？不应该是 O(V + E²) 吗？

通过尝试并实际执行代码，它显示时间复杂度为 O(V + E²)...我尝试运行并找到时间复杂度？我的错误是什么？

Answer 1

你写道：

如果我运行此代码，我会得到以下输出：

for循环运行的总次数：20

即 O(edges=5)² 那么时间复杂度 O(V+E) 是多少？不应该是 O(V + E²) 吗？

目前还不清楚你如何得出 O(edges=5)² 的结论，因为有 10 条边，而不是 5 条。而且 20 也不是 5²。

代码实际上在两个方向访问每条边，因此对于具有 10 条边的连通图，

for

循环将进行 20 次迭代。如果您有一个具有 1000 条边的连通图，则需要 2000 次迭代。

O(2E) 与 O(E) 相同（请参阅维基百科 - 大 O 表示法 - 乘以常数），因此总体时间复杂度符合预期：O(V+E)

一般来说，请注意，您无法通过“运行”程序来推导出程序的时间复杂度。这是通过分析代码并提供其复杂性的证明。