Kompyuter injiniringi” fakulteti “axborot ta’lim texnologiyalari” kafedrasi «taqsimlangan algoritmlar va tizimlar»

Amaliy qism:

1-rasm Linear search algoritmi

Chiziqli qidiruvda massiv va izlanayotgan element kiritiladi. Dastur qachonki o’sha x elementi topsagina to’xtaydi.

Chiziqli qidiruvning algoritmik tahlili:
Informatika fanida chiziqli qidiruv yoki ketma-ket qidiruv ro'yxatdagi elementni topish usulidir. Moslik topilmaguncha yoki butun ro'yxat qidirilmaguncha u ro'yxatning har bir elementini ketma-ket tekshiradi. 
Eng yomon murakkablik : O(n)
O'rtacha murakkablik : O(n)
Kosmik murakkablik : O(1)
Sinf : Qidiruv algoritmi

Yuqoridagi dasturda foydalanilgan massiv:

[13, 63, 39, 11, 59, 36, 64, 67, 73, 18, 69, 96, 57, 20, 50, 8, 26, 32, 37, 44, 101, 60, 63, 36, 12, 82, 98, 25, 86, 60, 15, 89, 70, 44, 18, 18, 95, 65, 58, 1, 52, 90, 41, 92, 22, 92, 75, 30, 7, 49, 32, 52, 58, 72, 65, 21, 43, 54, 14, 91, 21, 2, 32, 64, 13, 82, 90, 48, 76, 96, 11, 73, 65, 60, 81, 54, 51, 37, 92, 7, 26, 7, 58, 61, 91, 35, 28, 7, 8, 48, 71, 78, 90, 41, 63, 31, 25, 43, 27, 82]

Izlanayotgan elementni kiriting: 96
96 l massivning 11 indeksida joylashgan!
Binary search:

2-rasm Binary search
Dasturda foydalanilgan massiv:
[3, 3, 6, 6, 6, 7, 8, 8, 8, 8, 8, 9, 9, 10, 10, 11, 11, 13, 13, 14, 15, 16, 16, 16, 18, 19, 23, 26, 28, 29, 30, 32, 32, 33, 33, 34, 34, 35, 35, 36, 37, 39, 42, 42, 43, 43, 43, 45, 45, 46, 46, 47, 49, 55, 55, 56, 56, 56, 57, 60, 61, 64, 66, 66, 66, 67, 69, 69, 70, 70, 70, 71, 71, 79, 81, 81, 81, 83, 86, 86, 87, 87, 89, 90, 91, 92, 93, 93, 94, 94, 95, 95, 96, 98, 98, 99, 99, 100, 100, 101]
Izlanayotgan elementni kiriting: 14
14 l massivning 19 indeksida joylashgan!

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.
   

Dastur kodi:
def chiziqli_qidiruv(m, a):
l = len(m)
index = -1
for i in range(l):
if(m[i]==a):
index = i
print("Qidirilayotgan element", index, "- indeksda joylashgan!")
if index == -1:
print("Qidirilayotgan element massivda majvud emas!")
# Rustam Abduqahorov 1-amaliy ish
massiv = [21, 29, 1, 14, 22, 0, 27, 19, 17, 18]
item = int(input("Qidirilayotgan elementni kiriting:"))
chiziqli_qidiruv(massiv, item)


Xulosa
Linear Search va Binary Search, biron bir ro'yxatda qidirish uchun ishlatiladigan algoritmlardir. Bir nechta bir xil qiymatli elementlari bo'lgan katta ro'yxatlarda Binary Search algoritmi yuqori tezlik va samarali natijalar beradi. Buna qaramay, kichik ro'yxatlarda yoki soni kam ro'yxatlarda Linear Search algoritmi yaxshi natijalar olib chiqaradi.

Linear Search, ro'yxatni bajariladigan ikkita hodisa bor: (1) Barcha elementlarni tekshirish va (2) kerakli elementni topish. Bu algoritm ro'yxatni bajarishga imkon beradi, ammo ro'yxat hajmi katta bo'lganda va elementlar saralangan bo'lmaganida tezlikdan kechikishi mumkin.

Binary Search algoritmi esa, ro'yxatni ikki qismga ajratib, markaziy element bilan solishtiradi va kerakli elementni qidiradi. Agar qiymat markaziy elementdan kichik bo'lsa, qidiruvni ro'yxatning chap qismi bilan davom ettiradi. Aks holda, qidiruvni o'ng qismi bilan davom ettiradi. Algoritmning taqriban yarim taqdirdan keyin qiymatni topish mumkin bo'ladi. Bu algoritm O(log n) vaqtni talab qiladi va juda katta ro'yxatlarda yoki tezlik talab etilmaydigan holatlarda ishlatish tavsiya etiladi.

Xulosa qilish mumkinki, Linear Search kichik ro'yxatlarda yoki saralgan emas ro'yxatlarda yaxshi natijalar olib chiqaradi, Binary Search esa katta va saralgan ro'yxatlarda samarali va tezkor natijalar olib chiqaradi.

Foydalanilgan adabiyotlar
1. "Introduction to Algorithms" kitobi - Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein
2. "Algorithms, Part I" va "Algorithms, Part II" kurslari - Robert Sedgewick va
Kevin Wayne
3. "The Algorithm Design Manual" kitobi - Steven S. Skiena
4. "Algorithms Unlocked" kitobi - Thomas H. Cormen
5. "Grokking Algorithms" kitobi - Aditya Bhargava
6. "Data Structures and Algorithms in Python" kitobi - Michael T. Goodrich,
Roberto Tamassia va Michael H.