Algoritmlar nazariyasining boshlang’ich tushunchalari

Algoritm murakkabligi
Selection sort eng oddiy saralash algoritmlaridan bo’lib O(n²) vaqt tezligida ishlaydi. Ya’ni, algoritm barcha elementlarni ko’rib chiqish (n-1) mobaynida, har bir qadamda eng kichik elementni topish uchun qolgan elementlarni ko’rib chiqishi kerak bo’ladi. Matematik ko’rinishda quyidagicha bo’ladi:

4. 
   EKUBni qidirish algoritmi.
   

Evklid algoritmi - ikki sonni eng katta umumiy bo'luvchisini(EKUB) topib beruvchi effektiv algoritm hisoblanadi. Algoritm yunon matematiki Evklid nomiga berilgan. U bu algoritmni eramizidan 3 asr oldin o'ylab topgan. Evklid algoritmi ikkita musbat son uchun yangi juftlikni hosil qiladi, kattasini kichginasi orqali kamaytirib. Bu jarayon ikkala son teng bo'lib qolmaguncha davom ettiriladi.

Misol tariqasinda (12,14) juftligini olaylik. Dastlab 12 ni 14 olib tashlaymiz. Hosil bo'lgan juftlik - (12,2). Keyin shu jarayon taqrorlanadi:
����(12,2)=����(10,2)=����(8,2)=����(6,2)=����(4,2)=����(2,2)=2. Shunday qilib javob - 2. Bu algoritmini to'g'riligiga sabab agarda �=����(�,�) bo'lsa demak ikki sonni ayirmasi ham � soniga bo'linadi. Ya'ni (�−�)=0(��� �).
Afsuski, bu algoritm agarda birorta son kichik bo'lib, boshqasi katta bo'lsa juda ko'p amal bajarishiga to'g'ri keladi. Masalan (2,10000001) juftligi uchun 5000000 amal bajariladi ����i birligini aniqlash uchun. Ya'ni eng yomon holatda algoritm �(���(�,�)) amal bajarishiga to'g'ri keladi. Buni yanada tez ishlaydigan qilish mumkin. Gap shundaki har safar katta son kichkinasidan ���(�,�)/���(�,�) challi ayrilib tashlanadi. Ayirish o'rninga qoldiq olish amalini bajarish mumkin. Shunda har safar katta son kichginadan kichiklashadi. Har safar ikkala sondan bittasi kamida 2 baravar kichraygani uchun ishlash vahti �(���(���(�,�))) tashkil qiladi.
Lekin gap shundaki amalda bu algoritm deyarli �(1) amal bajaradi. Chunki har qanday juftlik uchun bittasi kamida ikki baravarga kichiklashadi dedik, ammo amalda bu kichrayish tezroq va kattaroq suratda bo'ladi. Masalan ushbu (12,14) juftlik uchun ����ni topish uchun 2 amal kifoya etadi . Lekin shunda ham shunday juftliklar bor-ki ular uchun algoritm ko'p amal bajarishi mumkin. Sizga bu masalada � soni berilgan bo'lib, siz shunday (�,�)1≤�<�≤� juftlikni topishingiz kerakki, bu juftliklar uchun Evklid algoritmi eng ko'p amalni bajarsin. Agarda bunday juftliklardan bir nechtasi bo'lsa � si minimalini chiqaring, agarda � si minimalidan bir nechta bo'lsa � si minimal bo'lganni chiqaring. Boshqacha qilib aytgan leksiografik eng kichik javobni chiqaring.

5. 
   Massivni tanlov usili bilan tartiblash.
   
1. 
   Massivni tartiblashtirishning bir necha usullari (algoritmlari) mavjud. Ulardan quyidagi usullarni qarab chiqamiz:
   -tanlash usuli;
   -almashtirish usuli.
   Tanlash usuli yordamida massivni o‘sish bo‘yicha tartiblashtirish algoritmi quyidagicha:
   1.Massivning birinchi elementidan boshlab qarab chiqilib eng kichik element topiladi.
   2.Birinchi element bilan eng kichik element joylari almashtiriladi.
   3.Ikkinchi elementidan boshlab qarab chiqilib eng kichik element topiladi.
   4.Ikkinchi element bilan eng kichik element joylari almashtiriladi.
   5.Bu protsess bitta oxirgi elementgacha takrorlanadi.
   Bu algoritm dasturi quyidagicha bo‘ladi:
   
2. 
   Program Sort;
   Const n=5;
   Var i, j, min, k, buf: Integer; a: Array[1..n] of Integer;
   Begin
   Writeln (‘Massivni tartiblashtirish’);
   Write (n:3,’ -ta massiv elementini kiriting’);
   For k:=1 to n Do Read(a[k]);
   For i:=1 to n-1 Do
   Begin { kichik elementni topish }
   min:=i;
   For j:=i+1 to n Do
   Begin
   If a[j]buf:=a[i]; a[i]:=a[min]; a[min]:=buf;
   For k:=1 to n Do Write (a[k],’ ‘);
   Writeln;
   End;
   End;
   Writeln(`Massiv tartiblashtirildi.`);
   End.
   
3. 
   Dastur natijasi:
   
4. 
   Massivni tartiblashtirish
   5 ta massiv elementini kiriting
   12 -3 56 47 10
   Tartiblatirish
   -3 12 56 47 10
   -3 10 56 47 12
   -3 10 12 47 56
   -3 10 12 47 56
   Massiv tartiblashtirildi.
   

1. 
   BubleSort dasturiy modulning tavsifi.