Qu'est-ce qui peut être la complexité de temps d'un algorithme qui calcule les poids des nœuds dans un graphique?
-
29-09-2020 - |
Question
J'essaie de trouver la meilleure complexité du temps d'un algorithme qui calcule les poids de tous les nœuds sur un graphique.Le poids du nœud est défini comme la somme des poids des bords adjacents.Je peux dire que l'algorithme est similaire à celui qui calculerait le degré de tous les nœuds et qui prend certainement O (| V | + | e |) mais pouvons-nous dire la même chose si nous essayons de calculer les poids denœuds?
La solution
for i in V:
weight(i) = 0
for e=(i,j) in E:
weight(i) = weight(i) + weight(e)
weight(j) = weight(j) + weight(e)
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange