Complexité temporelle de l'implémentation de l'algorithme de Prim suivant

Question

Quelle est la complexité temporelle du code suivant? J'implémente l'algorithme de prim avec la représentation de la matrice d'adjacence du graphe et de la file d'attente prioritaire. À mon avis, la complexité de temps est: le tas peut croître au maximum à la taille de (n-1), lorsque la source est connectée à tous les autres nœuds, et dans la boucle interne, la matrice d'adjacence coûte O (n), donc au total: son O ((n-1) * n) -> O (n^2), où n est le nombre de nœuds. Ce calcul est-il correct? Donc le tas n'améliore pas mon pire temps d'exécution en raison de la matrice d'adjacence?

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

Cela dépend de ce que fait le len (h), des valeurs qu'il retourne et du comportement du tout. Lorsque vous trouvez cela, vous le multipliez avec o (n) à partir du for et o (log n) de hq.headpush et vous obtenez votre complexité C'est quelque chose comme O (x * nlog n) où X est la marche à suivre le temps de finir.