Taqsimlangan tizimlarda qidiruv algoritmlar


Download 251.37 Kb.
bet6/6
Sana07.04.2023
Hajmi251.37 Kb.
#1339763
1   2   3   4   5   6
Bog'liq
Amaliy mashg’ulot 1

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.

  1. [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.

  2. [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.

  3. [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.

  4. [ 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.

  1. [ 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.

  1. [ 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.

  1. [ 94 29 25 24 12 23

3 50 91 83 55 63
71 8 89 37 70 37
59 95 66 15 48 46

  1. 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.



  1. Qidiruv algoritmini qanday turlari bor?

  2. Ketma-ket qidiruv algoritmi haqida aytib bering va misollar keltiring

  3. Intervalli qidiruv algoritmi haqida aytib bering va misollar keltiring

  4. Linear search algoritmini ustunliklari va kamchiliklarini ayting

  5. Binary search algoritmini ustunliklari va kamchiliklarini ayting

  6. Linear search algoritmini qadamlarini ayting va blok sxemasini chizing

  7. Binary search algoritmini qadamlarini ayting va blok sxemasini chizing

Download 251.37 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling