Comprendre le calcul de la complexité temporelle pour L'algorithme de Dijkstra

selon ma compréhension, j'ai calculé la complexité temporelle de L'algorithme de Dijkstra comme notation big-O en utilisant la liste de contiguïté ci-dessous. Cela ne s'est pas passé comme prévu et cela m'a amené à le comprendre pas à pas.

  1. chaque sommet peut être connecté aux sommets (V-1), donc le nombre d'arêtes adjacentes à chaque sommet est V - 1. Disons que E représente les bords V - 1 connectés à chaque sommet.
  2. trouver et mettre à jour le poids de chaque vertex adjacent en min tas est O(log(V)) + O(1) ou O(log(V)).
  3. ainsi, à partir des étapes 1 et 2 ci-dessus, la complexité temporelle pour mettre à jour tous les sommets adjacents d'un vertex est E*(logV). ou E*logV.
  4. donc la complexité temporelle pour tous les v vertices est V * (E*logV)I. e O(VElogV).

mais la complexité temporelle pour L'algorithme de Dijkstra est O (ElogV). Pourquoi?

37
demandé sur rd22 2014-10-24 16:24:19

1 réponses

l'algorithme du chemin le plus court de Dijkstra est O(ElogV) où:

  • V est le nombre de sommets
  • E est le nombre total d'arêtes

Votre analyse est correcte, mais les symboles ont des significations différentes! Vous dites que l'algorithme est O(VElogV) où:

  • V est le nombre de sommets
  • E est le nombre maximum d'arêtes attachés à une seule nœud.

renommez votre EN. Donc une analyse dit O(ElogV) et un autre dit O(VNlogV). Les deux sont corrects et en fait E = O(VN). La différence est que ElogV est une estimation plus précise.

51
répondu Shahbaz 2014-10-24 12:43:20