|
Algoritmlardalog(n) bu .
Masalann= bo’lganda taqqoslang:
O( ) = , O(n•log(n)) = 1660964.
Tanlash orqali saralash.
Bu sonlaro’rtasidajudakattafarq bor. Shuninguchun 2-tip algoritmlareffektivalgoritmlarhisoblanadi.
Algoritm ideasi massivning allaqachon saralangan qismiga saralanmagan qismidan navbatdagi eng kichik elementni qo’shib borish.
berilgan massiv.
1-qadam. 2<->4
2-qadam. 3<->9
3-qadam. 4<->7
(n-1) ta qadam yetarli.
Ishlash vaqti O(n2)
Asosiy masala massivning tartiblanmagan qismidan minimal element o’rnini aniqlash
for (int i = 1; i < n; i++) {
int min_id = i;
for (int j = i+1; j <= n; j++) {
if (a[j] < a[min_id])
min_id = j;
}
swap(a[i], a[min_id]);
}
Pufakcha usulida saralash(Bubble sort)
Umumiy n-1 martajarayonbajariladi. Harsafarikkitaqo’shni element taqqoslanadi.
Har bir iteratsiyada:
Agar ikkiqo’shni element noto’g’ri tartibda joylashib qolgan bo’lsa, ularning o’rnini almashtiramiz.
Elementlaro’zo’rinlarigapufakgao’xshabsiljibboradi.
Masalan:
Pufakchali saralash turg’un saralash hisoblanadi. Ya’ni qiymatlari bir xil bo’lgan elementlar saralangandan so’ng ham bir-biriga nisbatan tartibini saqlab qoladi. Berilgan massivdagi oldin joylashgan element saralangandan so’ng ham oldin joylashadi. Bu juda muhm hisoblanadi.
#include
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; i++)
cin>>a[i];
for (int i = n-1; i >= 1; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j+1]) {
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
for (int i = 0; i < n; i++)
cout<
return 0;
}
Ishlashvatqi ( ).
Taqqoshlashlarsoni ( ).
Almashtirishlarsoni ( ).
Qo’shimchaxotira .
Sanash orqalisaralash
Sanashorqalisaralashfaqatchekliqiymatlisonlarnisaralashmumkin. Masalan, massivning barcha elementlari qiymatlari 0..105intervalga tegishli bo’lsa.
Sanash orqali saralash uchun yordamchi massiv ochamiz, bu massiv har bir sondan qancha borligini saqlab turadi. Har bir songa kelganda uning sonini oshirish uchun yordamchi massivdan shu indeksning qiymatini 1 ga oshiramiz.
Keyin har bir 0..105 indekslarni birma-bir ko’rib bu sondan necha marta uchragan bo’lsa shuncha marta chiqaramiz.
Bunday saralash usuli massiv elementlarining maksimal qiymati massiv o’lchamiga nisbatan kichik bo’lganda ancha evvektiv bo’ladi.
Ishlash vaqti O(n+Max);
Qo’shimcha xotira O(Max);
Ikki o’zgaruvchining qiymatini almashtirish.
Topilgan minimal elementni o’rniga qo’yish uchun uni hozir buyerda turgan element bilan o’rnini almashtirish kerak. Buning uchun bizga ikki o’zgaruvchining qiymatlarini almashtirish kerak bo’ladi.
a va b ning qiymatlarini almashtirish uchun qo’shimcha t o’zgaruvchi kiritamiz va quyidagi amallarni bajaramiz:
t = a;
a = b;
b = t;
Qo’shimcha o’zgaruvchi kiritmasdan ham almashtirish mumkin buning uchun (o’zingiz tahlil qilib ko’ring):
a = a+b; (a+b, b);
b = a-b; (a+b, a);
a = a-b; (b, a);
C++ dasturlash tilida swap(a, b) funksiyasi orqalio’zgaruchilarning qiymatlarini almashtirish mumkin.
#include
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; i++)
cin>>a[i];
for (int i = 0; i < n-1; i++) {
intminPos = i;
for (int j = i+1; j < n; j++)
if (a[j] < a[minPos])
minPos = j;
int t = a[i];
a[i] = a[minPos];
a[minPos] = t;
}
for (int i = 0; i < n; i++)
cout<
}
minPos – minimal son turganindeks.
Ishlash vatqi ( ).
Taqqoshlashlar soni ( ).
Almashtirishlar soni .
Qo’shimcha xotira , ya’nito’zgaruvchiuchun.
10. Chiziqli qidiruv algoritmini massivda tushuntiring.
Qidiruv algoritmlari ichida ko`p ishlatiladigani chiziqli qidiruv algoritmlari.
Chiziqli qidiruv algoritmining kamchiligi agar so`rovlar soni m ta bo`lsa va har bir so`rov uchun n ta amal bajarsa taqqoslashlar soni n*m bo`ladi. Agar n va m larning qiymatlari n=m=105 ko`rinishida bo`lsa, u holda 1010 amal talab qilinadi. Buni esa EXM qisqa vaqt ichida bajara olmaydi
Binar qidiruv algoritmi biror berilgan sonni saralangan massivdan qidirish(bor yoki yo`qligini aniqlash) imkon beradi.
Binar qidiruv algoritmida har bir amalda izlanayotgan interval 2 marta kamayadi, demak k ta amaldan keyin 2k marta kamayadi. Massiv elementlari soni n ta bo`lsa 2k = n => k=log2(n) yani n ta elementli massivdan izlash log2(n) ta amal bajaradi.
Binar qidiruv algoritmini amalga oshirishda hamisha quyidagi sonlar mavjud.
L(left, chap) – izlanayotgan intervalning chap indeksi chegarasi.
R(right, o`ng) – izlanayotgan intervalning o`ng indeksi chegarasi.
M – izlanayotgan intervalning o`rtadagi element indeksi.
X = 32 – qidirilayotgan son.
L = 1, R = 12, m = (L+R)/2 = 6
O`rtadagi element 25 ga teng, 32≥25 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 6, R = 12, M = 9
O`rtadagi element 37 ga teng, 32<37 bo`lganligi uchun uni chap tomondan izlashni davom qildiramiz. L = 6, R = M =9, M = 7
O`rtadagi element 28 ga teng, 32≥28 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 7, R = 9, M = 8
O`rtadagi element 32 ga teng, 32≥28 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 8, R = 9.
R-L=1bo`lganida izlashni tugatamiz, izlanayotgan sonimiz L indeksda joylashgan massiv elementiga teng.
Do'stlaringiz bilan baham: |
