主页 / coding / 问题 / 78823597
Accepted
Sam J
Asked: 2024-08-02 10:29:25 +0800 CST

Dijkstra 的空间复杂度

  • 772

我正在研究一些关于 Dijkstra 算法的 Leetcode 问题，但我不太了解它的空间复杂度。我在网上查找，但找到了各种答案，有些答案相当复杂，所以我想知道我是否理解正确。

# initialize maxheap
maxHeap = [(-1, start_node)]
heapq.heapify(maxHeap)

# dijkstras algorithm
visit = set()
res = 0
while maxHeap:
    prob1,cur = heapq.heappop(maxHeap)
    visit.add(cur)

    # update result
    if cur == end_node: 
        res = max(res, -1 * prob1)

    # add the neighbors to the priority queue
    for nei,prob2 in adj_list[cur]:
        if nei not in visit: heapq.heappush(maxHeap, (prob1 * prob2, nei))

因为我使用一个visit集合和一个priority queue来跟踪节点，那么空间复杂度是否只是 O(V)，其中 V 是图中的顶点数？如果我必须使用一个在 Python 中生成邻接列表，那么空间复杂度是否会是dictO(E)，其中 E 是边数？

python

2 个回答

  1. 回答：

    1. 您的集合绝对不可能主导优先级队列。
    2. 如果邻接表对您有利（即，您获取了原始数据，例如，用人类语言描述，并且需要自己构建邻接表），那么它可能会或可能不会占主导地位，这取决于优先级队列的实现和图的属性。

    解释：

    Python 的 heapq 使用列表作为底层数据结构，您已经知道了这一点，就像 maxHeap = [(-1, start_node)] 一样。因此，它的空间复杂度为 Θ(n)，其中 n 是列表中元素的数量。

    那么数字是多少？它取决于图中的边与顶点，简而言之，如果顶点支配边，则为 O(V)，如果相反，则为 O(E)，但对于一般情况，我们可以将其表示为 O(V+E)。 它是 O(V+E) 而不是 O(V)，考虑到 V 与 E 之间的渐近关系，它可以进一步重写为 O(V^2)。

    为什么？因为您使用了 Python 的 heapq，它不提供 increamentKey/decreamentKey 操作，当您处理图时，您可能需要包含许多节点，但您还无法确定如何处理它。

    因此，集合永远不会占主导地位，因为它是 O(V)，在顶点占主导地位的最佳情况下，它只能与 heapq 打成平手。但是对于邻接表，如果您使用允许 decrementKey 操作的 DIY 版本优先级队列，因此您会得到 O(V) 空间复杂度，然后，如果 E 占主导地位 V，您将获得邻接表的 O(E)，而不是优先级队列的 O(V)。

    • 0
  2. Best Answer

    由于我使用访问集和优先级队列来跟踪节点，空间复杂度是否只是 O（V），其中 V 是图中顶点的数量？

    对于集合而言：是的。在最坏的情况下，目标是可以访问的最后一个节点，然后集合最终将为从起始节点可到达的每个节点提供一个条目，因此 O(𝑉')，其中 𝑉' 是您开始搜索的连接组件中的节点数。当图连通时，即 O(𝑉)。

    对于优先级队列：这并不能保证。由于您只在从队列中拉出节点时才将其标记为已访问，因此在给定时刻，队列中可能会出现多个相同的节点。调用次数的限制由边heappush数决定。因此，对于优先级队列，最坏情况下的空间复杂度为 O(𝐸)。

    如果我必须使用字典在 Python 中生成邻接表，那么其空间复杂度是否会为 O(E)，其中 E 是边的数量？

    这取决于您是否为没有传出边的节点创建字典键（以空列表作为值）。如果是这样，那么它就是 Θ(𝑉+𝐸)。如果您省略代表此类节点（没有传出边）的键，那么它确实是 Θ(𝐸)，但您的程序需要检查是否adj_list[cur]存在。

    其他备注

    • heapify如果列表只有一个元素，则无需调用。只有一个元素的列表已经是有效堆。

    • 当您从队列中弹出节点时，您应该验证它是否已被访问过。当一个节点在第一次出现之前被多次推送到队列中（因为它通过不同的路径遇到）时，可能会发生这种情况。在这种情况下，您会将其标记为已访问，因为第一次出现从队列中弹出，但最终它可能会被第二次弹出：然后您不应该处理它。

    • 当你找到目标节点，并且有 时res，你应该退出循环

    • 不要分配给res，而是将此代码包装在函数中并返回该值，这是一个很好的做法。

    所以：

    def dijkstra(adj, start_node, end_node):
    # initialize maxheap
    maxHeap = [(-1, start_node)]

    # dijkstra's algorithm
    visit = set()
    while maxHeap:
        prob1, cur = heapq.heappop(maxHeap)
        if cur in visit:
            continue
        visit.add(cur)

        # update result
        if cur == end_node: 
            return max(res, -1 * prob1)

        # add the neighbors to the priority queue
        for nei,prob2 in adj_list[cur]:
            if nei not in visit: 
                heapq.heappush(maxHeap, (prob1 * prob2, nei))

    return 0  # end_node not reachable
    • 0

相关问题