Internet va axborot kommunikatsiyasi fakulteti

Vaqtning murakkabligi
Dijkstra algoritmining murakkabligi ko'rilmagan cho'qqini asl cho'qqigacha minimal masofa bilan topish usuliga, ko'rilmagan cho'qqilar to'plamini saqlash usuliga va teglarni yangilash usuliga bog'liq. Grafikning uchlari soni n, m dan keyin esa qirralarning soni bo'lsin. Keyin, eng oddiy holatda, boshlang'ich cho'qqigacha minimal masofaga ega bo'lgan cho'qqini qidirish uchun butun cho'qqilar to'plami ko'rib chiqilsa va masofalarni saqlash uchun massiv ishlatilsa, algoritmning ishlash vaqti O (n) ga teng. 2). Asosiy sikl taxminan n marta bajariladi, ularning har birida minimalni topish uchun n ga yaqin amallar sarflanadi. Qirralarning soniga mutanosib bo'lgan operatsiyalar soni m (chunki har bir chekka ushbu tsikllarda ikki marta sodir bo'ladi va doimiy son operatsiyalarni talab qiladi) har bir tashrif buyurilgan cho'qqining qo'shnilari bo'ylab halqalarga sarflanadi. Shunday qilib, algoritmning umumiy ishlash vaqti O (n 2 + m), lekin m n (n-1) dan ancha kichik bo'lgani uchun, oxirida biz O (n 2) ni olamiz.
Noyob grafiklar uchun (ya'ni, m n² dan ancha kichik bo'lganlar uchun) ko'rilmagan cho'qqilarni ikkilik to'plamda saqlash mumkin va masofa qiymatlari kalit sifatida ishlatilishi mumkin. Tsikl n martalik tartibda bajarilganligi va bo'shashishlar soni (yorliqlarning o'zgarishi) m dan ortiq bo'lmaganligi sababli, bunday amalga oshirishning ishlash vaqti O (nlogn + mlogn) ga teng.
Misol

1-cho'qqigacha bo'lgan masofani bosib o'tiladigan cho'qqilar bo'yicha hisoblash:

eng qisqa yo'l bugungi kunda bu hayotiy vazifa bo'lib, deyarli hamma joyda, yerdagi ikkita ob'ekt o'rtasidagi optimal marshrutni topishdan boshlab (masalan, uydan universitetgacha bo'lgan eng qisqa yo'l), avtopilot tizimlarida transport, kommutatsiya uchun optimal marshrutni topish uchun ishlatiladi. tarmoqlardagi ma'lumotlar paketi va boshqalar.
Eng qisqa yo'l grafik deb ataladigan ba'zi bir matematik ob'ekt yordamida ko'rib chiqiladi. Qidirmoq eng qisqa yo'l grafikdagi ikkita berilgan cho'qqi o'rtasida olib boriladi. Natijada yo'l, ya'ni ikkita qo'shni cho'qqiga tushadigan cho'qqilar va qirralarning ketma-ketligi va uning uzunligi.
Eng uchtasini ko'rib chiqing samarali algoritm topish eng qisqa yo'l:

• 
  Dijkstra algoritmi;
  
• 
  Floyd algoritmi;
  
• 
  ro'yxatga olish algoritmlari.
  

Ko'rsatilgan algoritmlar grafikdagi oz sonli uchlari bilan osongina bajariladi. Ularning sonining ko'payishi bilan qidiruv vazifasi eng qisqa yo'l murakkablashadi.


Xulosa
Algoritm holatini hozirgi vaqtda bajarilayotgan buyruq manzili va barcha o'zgaruvchilarning qiymatlari deb ataymiz, bu jarayon holati vektoriga tengdir. Shuning uchun ko'pgina algoritmlar deterministikdir, ya'ni ularda har qanday holat uchun faqat bitta yo'l qo'yiladigan keyingi holat mavjud (shart va tanlash operatsiyalari). Bu shuni anglatadiki, bunday algoritm bir vaqtning o'zida bitta narsani bajarishi mumkin.
Algoritmning vaqt murakkabligi funktsiyasi ba'zi holatlarda aniq aniqlanishi mumkinligiga qaramasdan, aksariyat hollarda uning aniq qiymatini izlashning ma'nosi yo'q. Gap shundaki, birinchidan, vaqt murakkabligining aniq qiymati elementar operatsiyalarni aniqlashga bog'liq (masalan, murakkablikni arifmetik operatsiyalar yoki Turing mashinasidagi operatsiyalar sonida o'lchash mumkin), ikkinchidan, kirish ma'lumotlari hajmining ko'payishi, doimiy omillar va atamalarning hissasi. ishning aniq vaqti uchun ifodada paydo bo'lgan pastki buyurtmalar juda ahamiyatsiz bo'ladi.
Katta o'lchamdagi kirish ma'lumotlarini ko'rib chiqish va algoritmning ishlash vaqtining o'sishi tartibini baholash algoritmning asemptomatik murakkabligi tushunchasiga olib keladi. Bundan tashqari, pastki asimptotik murakkablikdagi algoritm, barcha ma'lumotlarni kiritish uchun samaralidir, ehtimol kichik ma'lumotlardan tashqari.
Algoritmlarni saralash jarayonini amalga oshirishda oldingi qatorga juda ko'plab amaliy muammolar chiqadi. Ko‘plab saralash dasturi ishlab chiquvchilarni tanlash shu yoki boshqa vaziyatlarda juda ko'p faktlarga bo‘g‘liq bo‘lishi mumkin. Juda ko‘p shunga o ‘xshash masalalar hal qiiishda “kodlami sozlash” dan ko‘ra '‘algoritmlar” darajasidan foydalanish maqsadga muvofiqdir.