Mavzu: Prima-Deyskrita Algaritmi. Uni vaqt bo`yicha baholash

Algoritmning murakkabligi
Dijkstra algoritmining murakkabligi v cho'qqisi qanday topilganiga, ko'rilmagan cho'qqilar to'plami qanday saqlanishiga va teglar qanday yangilanishiga bog'liq. G grafigining uchlari sonini n, qirralarning sonini m bilan belgilang.
Eng oddiy holatda, minimal d[v] cho'qqisini topish uchun butun cho'qqilar to'plami qidirilsa va d qiymatini saqlash uchun massiv ishlatilsa, algoritmning ishlash vaqti {\displaystyle O bo'ladi. (n^{2})}O(n^{2} ). Asosiy sikl taxminan n marta bajariladi, ularning har birida minimalni topish uchun n ga yaqin amallar sarflanadi. Har bir tashrif buyurilgan cho'qqining qo'shnilari bo'ylab velosipedda o'tish m qirralarning soniga mutanosib bo'lgan bir qator operatsiyalarni oladi

(chunki har bir chekka bu tsikllarda ikki marta sodir bo'ladi va doimiy sonli operatsiyalarni talab qiladi). Shunday qilib, algoritmning umumiy ishlash vaqti {\displaystyle O(n^{2}+m)}O(n^{2}+m), lekin {\displaystyle m\leq n(n-1)} m \leq n(n-1), u {\displaystyle O(n^{2})}O(n^{2}).

Noyob grafiklar uchun (ya'ni, m n² dan ancha kichik bo'lganlar uchun) ko'rilmagan cho'qqilarni ikkilik to'plamda saqlash mumkin va d[i] ning qiymatlari kalit sifatida ishlatilishi mumkin, keyin cho'qqi {\displaystyle {\overline {U}}} \overline U bo'ladi {\displaystyle \log n}\log n, o'zgartirish vaqti {\displaystyle d[i]}d[i] ga ko'tariladi {\displaystyle {\overline {U}}} \displaystyle \log n}\log n. Tsikl n martalik tartibda bajarilganligi va yorliq o‘zgartirishlar soni ko‘pi bilan m bo‘lganligi sababli, bunday amalga oshirishning ishlash vaqti {\displaystyle O(n\log n+m\log n)}O(n). \log n+m\log n).
Agar biz ko'rilmagan cho'qqilarni saqlash uchun Fibonachchi to'plamidan foydalansak, ular uchun o'chirish o'rtacha {\displaystyle O(\log n)}O(\log n) da sodir bo'ladi va {\displaystyle O(1)}O() da o'rtacha pasayish sodir bo'ladi. 1 ), keyin algoritmning ishlash vaqti {\displaystyle O(n\log n+m)}O(n\log n+m) boʻladi.