Време за изпълнение на алгоритъма на Дейкстра - приоритетна опашка (купчина)

Трудно ми е да разбера защо сложността на алгоритъма на Дейкстра с купчина е O( (m + n)*log(n)), където m е броят на ръбовете, а n е броят на върховете.

Моето разбиране е:

Сега знам, че човек трябва да направи n премахване на минути. (Всяка мин. премахване отнема log(n) от купчина).

Тогава човек трябва да направи m ключове за актуализиране. (Всеки ключ за актуализиране взема log(n)).

Оттук и отговорът. Ясна ли е концепцията ми? В противен случай можете ли да обясните как да получите времевата сложност на алгоритъма на Дейкстра.


algorithm time-complexity dijkstra
person S. Salman    schedule 04.05.2015    source източник
comment
Сложността на Dijsktra с куп е O(m+ n*log(n)) (вижте en.wikipedia. org/wiki/Dijkstra%27s_algorithm), а не O((m+n) log(n), така че вашето разсъждение изглежда правилно.   -  person Rafał Dowgird    schedule 04.05.2015
comment
Не използвам Fibonacci Heap.   -  person S. Salman    schedule 04.05.2015
comment
Този раздел прави изчисленията за други типове купчини: en.wikipedia.org/wiki/Dijkstra %27s_algorithm#Running_time   -  person Rafał Dowgird    schedule 04.05.2015
comment
Да, вашият анализ е правилен за двоична купчина.   -  person Niklas B.    schedule 04.05.2015

Отговори (1)


arrow_upward
0
arrow_downward

Сложността варира леко в зависимост от начина, по който прилагате Dijkstra с помощта на heap. Например използвам вградената опашка с приоритети в c++ и тази купчина не поддържа приоритетна актуализация. Така всеки път, когато искам да актуализирам приоритета на даден елемент, просто избутвам още един елемент в купчината. Това може да накара моята купчина да стане с размер m (все пак всяко вмъкване/изскачане има сложност O(log(m)), което е същото като O(log(n))).

Ако използвате Fibonacci heap, можете да намалите сложността на алгоритъма.

Ако използвате обикновена двоична купчина, вашият анализ е почти правилен - трябва да натиснете m елемента в купчина, която поддържа вмъкване/изскачане в O(log(n)). Също така трябва да премахнете минималния елемент поне n пъти.

person Ivaylo Strandjev    schedule 04.05.2015