13.1. Graflarda eng qisqa yo’lni toppish algoritmlari. Graflarda eng qisqa yo'lni topishning eng samarali algoritmlari Dijkstra algoritmi, Floyd algoritmi va Bulkhead algoritmlarini o'z ichiga oladi. Ushbu algoritmlar juda oz sonli vertikalar uchun samarali.
Dijkstra algoritmini amalga oshirishda dastlabki tepadan eng qisqa yo'llar allaqachon ma'lum bo'lgan ko'plab vertikalar qurilgan. Quyidagi qadamlar optimal yo'llarning uzunligini saqlab, mavjud bo'lgan to'siqlarga bir tepalikka qo'shilishga asoslangan.
Dijkstra algoritmining murakkabligi vertikani topish usuliga, shuningdek, ko'plab turg'un cho'qqilarni saqlash usuli va uzunliklarni yangilash usuliga bog'liq.
Floyd usuli, qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan eng qisqa yo'l boshqa eng qisqa yo'llardan iboratligiga asoslanadi.
Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, Floyd algoritmining ishlash vaqti o(n3) tartibiga ega.
Bulkhead algoritmlar optimal yechim topish uchun algoritmlar bor.
To'lqin algoritmi kenglikdagi qidiruvga asoslangan va ikki bosqichdan iborat: to'lqin tarqalishi va teskari harakat.
Keng qidirish usuli bilan qidirish, qaytib kelish bilan solishtirganda, ma'lumotni saqlash uchun ko'proq yordamchi xotira talab qiladi, biroq u tezroq ishlaydi, chunki bir xil tepalikka bir martadan ko'proq tashrif buyurilmaydi.
14.1 Tezkor saralash(Quick sort) Quicksort - bu joydagi tartiblash algoritmi. 1959-yilda ingliz kompyuter olimi Toni Xoar tomonidan ishlab chiqilgan[1] va 1961-yilda nashr etilgan[2], bu hali ham tartiblash uchun keng tarqalgan algoritmdir. Yaxshi amalga oshirilganda, u birlashma tartiblashdan biroz tezroq va yig'ma tartibdan ikki yoki uch barobar tezroq bo'lishi mumkin.[3][qaramas].
Quicksort - bu bo'lish va zabt etish algoritmi. U massivdan “pivot” elementini tanlash va boshqa elementlarni pivotdan kichik yoki kattaligiga qarab ikkita kichik massivga bo‘lish orqali ishlaydi. Shu sababli, uni ba'zan bo'lim-almashinuv tartibi deb ham atashadi.[4] Keyin pastki massivlar rekursiv tartiblanadi. Bu saralashni amalga oshirish uchun kichik qo'shimcha xotira hajmini talab qiladigan joyda amalga oshirilishi mumkin.
Tezkor saralash solishtirish tartibidir, ya'ni u "kamroq" munosabati (rasmiy ravishda umumiy tartib) belgilangan har qanday turdagi elementlarni saralashi mumkin. Quicksort-ning samarali qo'llanilishi barqaror tur emas, ya'ni teng tartiblash elementlarining nisbiy tartibi saqlanib qolmaydi.
Tezkor saralashning matematik tahlili shuni ko'rsatadiki, o'rtacha hisobda algoritm n ta elementni saralash uchun {\displaystyle O(n\log {n})}O(n\log {n}) taqqoslashlarini oladi. Eng yomon holatda, u {\displaystyle O(n^{2})}O(n^{2}) taqqoslashni amalga oshiradi.
