Taqsimlangan tizimlarda qidiruv algoritmlar
Amaliy mashg’ulot 1
- Bu sahifa navigatsiya:
- O(1) dir. Average Case Complexity
- O(logn) dir. 1.7-rasm. Binary search algoritmi blok sxemasi Amaliy topshiriqlar.
| Eng yomon holat
|
|
O (logn) |
Eng yaxshi holat murakkabligi - Ikkilik qidiruvda eng yaxshi holat birinchi taqqoslashda qidiriladigan element topilganda, ya'ni birinchi o'rta elementning o'zi izlanadigan element bo'lganda paydo bo'ladi. Ikkilik qidiruvning eng yaxshi vaqt murakkabligi O(1) dir.
Average Case Complexity - Ikkilik qidiruvning o'rtacha ish vaqti murakkabligi O(logn) dir.
Eng yomon holatlarning murakkabligi - Ikkilik qidiruvda, eng yomon holat, biz qidiruv maydonini faqat bitta elementga ega bo'lgunga qadar qisqartirishimiz kerak bo'lganda yuzaga keladi. Ikkilik qidiruvning eng yomon vaqt murakkabligi O(logn) dir.
1.7-rasm. Binary search algoritmi blok sxemasi
Amaliy topshiriqlar.
[21 29 1 14 22 0 27 19 17 18] ushbu massive uchun chiziqli algoritmdan foydalanib python yoki c++ dasturlash tilida berilgan elementni qidirish dasturini yozing.
[59 18 25 31 29 51 77 41 0 40 37 25 55 36 33] ushbu massive uchun chiziqli algoritmdan foydalanib python yoki c++ dasturlash tilida berilgan elementni qidirish dasturini yozing.
[63 29 72 5 12 84 21 85 9 51 94 41 27 10 76 60] ushbu massive uchun chiziqli algoritmdan foydalanib python yoki c++ dasturlash tilida berilgan elementni qidirish dasturini yozing.
[ 76 66 92 57 50 73
35 49 60 95 41 84
76 48 97 91 7 75
90 44 3 72 54 62
39 94 69 86 48 0
65 76 61 97 18 16] ushbu massive uchun chiziqli algoritmdan foydalanib python yoki c++ dasturlash tilida har bir satrdan eng katta elementni qidirish dasturini yozing.
[ 76 66 92 57 50 73
35 49 60 95 41 84
76 48 97 91 7 75
90 44 3 72 54 62
39 94 69 86 48 0
65 76 61 97 18 16] ushbu massive uchun chiziqli algoritmdan foydalanib python yoki c++ dasturlash tilida har bir ustundan eng katta elementni qidirish dasturini yozing.
[ 94 29 25 24 12 23
3 50 91 83 55 63
71 8 89 37 70 37
59 95 66 15 48 46
42 84 17 38 64 35
47 39 84 13 84 100] ushbu massive uchun chiziqli algoritmdan foydalanib python yoki c++ dasturlash tilida har bir satrdan eng katta elementni qidirish dasturini yozing.
[ 94 29 25 24 12 23
3 50 91 83 55 63
71 8 89 37 70 37
59 95 66 15 48 46
4 17 38 64 35
47 39 84 13 84 100] ushbu massive uchun chiziqli algoritmdan foydalanib python yoki c++ dasturlash tilida har bir ustundan eng katta elementni qidirish dasturini yozing.
Nazorat savollari.
Qidiruv algoritmini qanday turlari bor?
Ketma-ket qidiruv algoritmi haqida aytib bering va misollar keltiring
Intervalli qidiruv algoritmi haqida aytib bering va misollar keltiring
Linear search algoritmini ustunliklari va kamchiliklarini ayting
Binary search algoritmini ustunliklari va kamchiliklarini ayting
Linear search algoritmini qadamlarini ayting va blok sxemasini chizing
Binary search algoritmini qadamlarini ayting va blok sxemasini chizing
Download 251.37 Kb.
Do'stlaringiz bilan baham:
