Sıralı liste/dizi tarafından uygulanan bir öncelik sırasına göre Dijkstra'nın algoritması için çalışma süresi

Question

Bu yüzden, sıralı bir liste/dizi tarafından uygulanan öncelik sırasındaki algoritmanın çalışma zamanının ne olduğunu bilmek istiyorum. Listelenmemiş bir liste/dizi için biliyorum O ((n^2 + m)), burada n köşe sayısı ve kenar sayısıdır. Böylece O (n^2) zamana eşittir. Ama sıralı bir liste/dizi kullansaydım daha hızlı olurdu ... Çalışma süresi ne olurdu? Özütlemenin sürekli zaman olacağını biliyorum.
hep birlikte sıralı bitişiklik listelerini birleştirme:

Answer 1

Peki, o zaman (örnek O (VlogE) için, genellikle köşeleri ve kenarları V ve E gibi kullanılır, ileride başvurmak üzere) Dijkstra'nın algoritması için gerekenleri gözden geçirelim O (e)
özü az: O (1)
azalış anahtar: bu yüzden, O (V) '
Dijkstra O (V kullanır) en az işlemleri özü ve O (E) anahtar işlemleri azaltmak:
O (1) * O (V) = O (V)
O (E) * O (V) = 0 (EV) = 0 (V^2)
En asimptotik olarak önemli bir kısmı almak:
Ardışık asimptotik çalışma zamanı O (V^2).
Bu daha iyi yapılabilir mi? Evet. İkili yığınlara ve öncelik sıralarının daha iyi uygulanmasına bakın.

Edit: Aslında bir hata yaptım, şimdi tekrar bakıyorum. E, V^2'den daha yüksek olamaz, başka bir deyişle E = O (V^2) olamaz.
nedenle, en kötü ihtimalle, biz (EV) O'da ishal sonucuna algoritma aslında O (V^2 * V) == O (V^3)

Answer 2

Ben http://blog.devarchive.net/2013/03/fast-dijkstras-algorithm-inside-ms-sql.html It SortedList kullanmak Yineleme başına bir kez listeleme listesinden 20-50 kat daha hızlıdır