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

以下代码的时间复杂度是多少？我正在用图和优先级队列的邻接矩阵表示来实现prim的算法。在我看来，时间复杂度是：当源连接到每个其他节点时，堆的最大增长可达到（n-1）的大小，并且在内部循环中，邻接矩阵的成本为O （n），因此总共为：其O（（n-1）* n）→O（n^2），其中n是节点的数量。这个计算是否正确？所以堆不能改善我的最坏情况运行时间，因为邻接矩阵？以下Prim算法实现的时间复杂度

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

来源

2017-07-12 Hasan Iqbal Anik

您认为时间复杂度是多少？为什么？我们不在这里为你做你的工作。 – Barmar

我已更新问题以包含我的计算 –

您遗漏了“为什么”部分。 – Barmar

这取决于len（h）的作用，它返回的值以及该行为的表现。当你发现这一点时，你将它与来自hq.headpush的for和o（log n）的o（n）相乘，你就会得到复杂度它就像O（x * nlog n），其中X是它需要的步骤完成时。

来源

2017-07-12 16:27:44 Catalin

len（h）应该是O（1）操作。它只是返回堆的长度。 –

这段时间的目的是什么？只要你有堆就跑？ – Catalin

是的。只要堆中有元素。 –

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

回答

相关问题