Le Grand O sur la Dijkstra Fibonacci tas solution
De Wikipédia: O(|E| + |V| log|V|)
De Big O Cheat List: O((|V| + |E|) log |V|)
Je considère qu'il y a une différence entre E + V log V
et (E+V) log V
, n'est-ce pas?
Parce que, si Wikipédia est correct, il ne devrait pas être montré comme O(|V| log |V|)
ensuite seulement (Retrait |E|
) pour une raison que je ne comprends pas?)?
Qu'est-ce que le Grand O de Dijkstra avec Fibonacci Tas?
Vous devez vous connecter pour publier un commentaire.
La complexité de Dijkstra plus court chemin algorithme est:
où
Q
est le min de file d'attente de priorité de commande des sommets par leur distance actuelle estimation.À la fois d'un tas de Fibonacci et un tas binaire, la complexité de l'extraire-min opération sur cette file d'attente est
O(log |V|)
. C'est ce qui explique la commune|V| log |V|
partie de la somme. Pour une file d'attente mis en œuvre avec un tableau non-trié, les extraire-min opération aurait une complexité deO(|V|)
(l'ensemble de la file d'attente à traverser) et à la présente partie de la somme seraO(|V|^2)
.Dans la partie restante de la somme (l'un avec le bord facteur |E|), le
O(1)
c. s.O(log |V|)
différence provient précisément de l'aide respectivement d'un tas de Fibonacci, par opposition à un tas binaire. La diminution de la touche de fonctionnement qui peut se produire pour chaque arête a exactement cette complexité. De sorte que le reste de la somme a, finalement, la complexitéO(|E|)
pour un tas de Fibonacci etO(|E| log |V|)
pour un tas binaire.Pour une file d'attente mis en œuvre avec un tableau non-trié, la diminution de la touche de fonctionnement aurait une constante de temps de la complexité (la file d'attente directement stocke les clés indexés par les sommets) et cette partie de la somme serait donc
O(|E|)
, qui est aussiO(|V|^2)
.Pour résumer:
O(|E| + |V| log |V|)
O((|E| + |V|) log |V|)
O(|V|^2)
Puisque, dans le cas général
|E| = O(|V|^2)
, il ne peut pas être simplifiée davantage, sans faire d'autres hypothèses sur le type de graphiques traitées.decrease-key(Q)
) de Fibonacci-tas estO(1)
puis nous avonsO(E + V log V)
et binaire-tas estO(log V)
nous avons doncO((E+V) log V) = O(E log V + V log V)
. Si c'est correct, je ne peux pas dire que Fibonacci-tas est justeO(V log V)
commeE
est en faitO(1)
?O(E + V log V)
àO(V log V)
(à moins de faire quelques hypothèses supplémentaires sur le type de graphiques que vous avez à traiter avec des).In the remaining part of the sum, the O(1) v.s. O(log(|V|)) difference
? Sur la Dijkstra tableau non trié lesO(E + V^2)
est simplifié à l'O(V^2)
, n'est-ce pasE
le même cas ici?|decrease-key(Q)|
opération estO(1)
avec un tas de Fibonacci etO(log(|V|))
avec un tas binaire. Total, il y aO(|E|)
diminution des opérations à clé. Avec un tableau non-trié,decrease-key(Q)
estO(1)
, mais il y a encoreO(|E|)
diminution des opérations à clé. Toujours avec un tableau non-trié,extract-min(Q)
estO(|V|)
. D'où laO(|E| + |V|^2)
de la complexité de l'algorithme de Dijkstra avec un tableau non-trié. Cependant, comme je l'ai écrit précédemment,|E|
estO(|V|^2)
, donc cela peut être encore simplifié à justeO(|V|^2)
.|E| = O(|V|^2)
" je ne peux pas l'expliquer à moi-même pour le moment. Aussi, pour les ménagères de tableau, quand il estO(|E| + |V|^2)
et|E|
est également|V|^2
il obtientO(2|V|^2|)
, mais parce que nous n'avons pas de soins pour les constantes, c'est pourquoi nous l'enlever? Et dernière question - si|E| = O(|V|^2)
ne devrions-nous pas écrire qu'au lieu de|E|
?|E| = O(|V|^2)
? Combien d'arêtes dans le pire des cas, vous pouvez avoir dans un graphe avec|V|
sommets? Juste un lien de chaque sommet de chaque autre sommet. De sorte que chacun des |V| vertex est lié à |V| - 1 autres sommets et vous ne voulez pas compter deux fois les bords, donc dans ce cas le pire scénario |E| = |V| (|V| - 1) / 2 = O(|V|^2).O(|V|^2)
au lieu deO(|E|)
? Vous voulez peut-être savoir quelles sont les parties de votre formule dépend du nombre de bords si vous n'êtes pas affaire avec les pires cas de graphes. Il est judicieux de remplacerO(|E|)
avecO(|V|^2)
quand un autre terme dans la complexité se cache cette substitution (a ou plus de complexité queO(|V|^2)
): par exemple, dans la complexité pour le tableau non trié cas.|E|
j'ai entendu que le total des arêtes du graphe. Dans le pire des cas je le vois il|E|=O(|V|^2)
. Cependant, ce sujet de grilles rectangulaires? Il est généralement dit que Dijkstra estO=(|V| log|V|) for these grids and therefore I assume that
|E| " peut être "supprimé", mais pourquoi?|E|=O(|V|)
(par exemple, un N x M grille avec |V| = N M sommets a |E| = N (M - 1) + M (N - 1) = O(N M) = O(|V|) les arêtes). Par conséquent, sur une telle grille, Dijkstra avec un tas de Fibonacci estO(|V| + |V| log |V|) = O(|V| log |V|)
et Dijkstra avec un tas binaire estO((|V| + |V|) log |V|) = O(|V| log |V|)
. Dans les deux cas,|E|
"disparaît" (soit d'être dominé par un autre terme ou parce qu'il ne pas ajouter quoi que ce soit).Dijkstra est O(|E| + |V| log|V|) avec des tas de Fibonacci et O (|V| + |E|) log |V|) sans elle.
Correct, d'une certaine façon. Big O Cheat Liste montrant les plus communs de mise en œuvre et Wiki le meilleur il est.
O(|E| + |V| log|V|) n'est pas en O(|V| log|V|) btw. E est en O(|V|^2), pas de O(|V| log|V|).