Hisoblash modellari, algoritmlar va ularning murakkabligi Algoritm tushunchasi. Avvalo algoritm

(1) for(int i=0; i
{
(2) min1=A[i]; n
(3) k=i; n-1
(4) for(int j=i+1; j
(5) if(min1>A[j]){ (n2+3n)/2
(6) min1=A[j]; 0 dan (n2+3n)/2 gacha
(7) k=j; 0 dan (n2+3n)/2 gacha
(8) }
(9) A[k]=A[i]; n-1
(10) A[i]=min1; n-1
(11) }
4-operatorning bahosi quyidagicha olinadi. Ushbu sikl sarlavhasi har bir i uchun bajariladi va i = 0 uchun n+1 marta, i = 1 uchun n marta, n-1, n-2, ..., 0 marta bajariladi. Ya‘ni, bizda a1, a2, ..., am arifmetik progressiyasi bor, ularning yigʻindisi
26
Bu yerda m = n+1, a1 = n+1, am = 1 va yigʻindisi (n2+3n-2)/2.
5-operatorning bahosi xuddi shu tarzda olinadi, shunchaki unutmang for siklining asosiy qismi har doim tanasiga qaraganda yana bir marta bajariladi. Bu yerda .
6- va 7-operatorlarning baholariga kelsak, biz bunga oldinroq duch kelganmiz.
Kiritilgan ma‘lumotlarga qarab, ushbu operatorlar boshqacha marta bajarilishi mumkin. "Yaxshi" ma‘lumotlar uchun (massiv allaqachon saralangan boʻlsa), bu operatorlar hech qachon bajarilmaydi. "Yomon" ma‘lumotlar uchun ushbu operatorlar har bir tekshirishda min>a[j] bajariladi. Algoritmlarni saralash uchun "yomon" ma‘lumotlar teskari tartibda saralangan massivdir.
Shunday qilib, saralash algoritmi uchun eng yaxshi ball n2 + 8n-5, eng yomon koʻrsatkich esa 2n2+11n-5. Yomonmi yoki yaxshimi? Hozircha faqat massiv allaqachon saralangan boʻlsa, algoritm koʻp vaqt sarflashini sezishingiz mumkin. Bu ushbu algoritmning aniq kamchiliklaridir.
6-§. Graflar nazariyasi elementlari va o'tish algoritmlari
Graflarni oʻrganish bilan shugʻullanadigan diskret matematikaning boʻlimi ―Graflar nazariyasi‖ deb ataladi. Graflar nazariyasida ushbu matematik obyektlarning asosiy tushunchalari, xususiyatlari, tasvirlash usullari va qoʻllanilish sohalari batafsil koʻrib chiqilgan. Bizni faqat dasturlashda muhim boʻlgan jihatlari qiziqtiradi.