以下Prim算法实现的时间复杂度

Question

以下代码的时间复杂度是多少？我用图和优先级队列的邻接矩阵表示来实现prim的算法。在我看来，时间复杂度是：当源连接到每个其他节点时，堆最多可以增长到（n-1）的大小，而在内部循环中，邻接矩阵的成本是O（n），因此，总的来说：它的O（（n-1）*n）-

from graph import adj_mtx, AP
import heapq as hq

lv, visited, h = float('inf'), {}, []  # lv stands for 'large_value', h is the heap


def prims_mst(adj_matrix, src):
    hq.heappush(h, (0, (src, None)))  # O(logn)
    curr_dist = {item.value: lv if item.value != src else 0 for item in AP}  # AP is the enumeration of nodes

    while len(h) != 0:
        curr_nd = hq.heappop(h)[1][0]  # first element of the tuple is the value, second is the node  # O(1)
        visited[curr_nd] = True  # O(1)
        for nd, dst in enumerate(adj_matrix[src]):  # O(n) -> n is the number of nodes
            if nd not in visited and curr_dist[nd] > curr_dist[curr_nd] + adj_matrix[curr_nd][nd]:
                curr_dist[nd] = curr_dist[curr_nd] + adj_matrix[curr_nd][nd]
                hq.heappush(h, (curr_dist[nd], (nd, curr_nd)))  # O(logn)
        print h

Answer 1

这取决于len（h）做什么，它返回什么值，以及and的行为。当您发现这一点时，将其与for中的o（n）和hq.headpush中的o（log n）相乘，您就会得到复杂性。它类似于O（x*nlog n），其中X是完成一段时间所需的步骤。