“axborot ta’lim texnologiyalari” kafedrasi "Taqsimlangan aloritmlar va tizimlar" fanidan


Download 292.43 Kb.
Pdf ko'rish
bet2/2
Sana11.03.2023
Hajmi292.43 Kb.
#1261392
1   2
Bog'liq
1-Amaliy topshiriq

Xulosa. 
Linear search algoritmi ro'yxatni elementlariga bo'shatish bilan boshlanadi va har bir 
elementni tekshiradi, shunchaki qidiruvni to'g'ridan-to'g'ri bajaradi. Bu, ma'lumotlar 
ro'yxati uzunroq bo'lsa yoki elementlarning tartiblanganligi bo'lmagan holda yuqori ishchi 
zaxiralarni talab qiladi. Ammo, agar ro'yxat kichik bo'lsa, yoki qidiruv bo'yicha kerakli 
elementni o'z ichiga olgan elementlar juda kam bo'lsa, linear search osonlik bilan amalga 
oshirilishi mumkin. 
Binary search algoritmi esa ro'yxatning yarmi orqali tekshiriladi va yarmi orqali chop 
qilingan ro'yxatlarga bo'shatish bilan boshlanadi. Bu, ro'yxatning sarflanganligidan 
foydalanib elementlarni ajratadi va yarmi orqali tekshiradi. Bunday holatda, har bir 
tekshiruvda qidirilayotgan element ro'yxatning yarmi orqali ajratiladi va tekshiruv 
o'zining birinchi yarmida amalga oshiriladi. Bundaylik bilan, binary search algoritmi 
yuqori ishchi zaxiralarga talab qilmasligi uchun, ma'lumotlar ro'yxatining uzunligi nechta 
bo'lsa ham muhim bir darajada ishlaydi. 
Quyidagi jadval linear va binary search algoritmlari o'rtasidagi farqni tushuntiradi: 
Algoritm 
Avvalgi 
sarflaganlik 
Qidiruv 
zaxiralari 
Sarflanganlik 
Linear 
search 


O(n) 
Binary 
search 
log_2(n) 
log_2(n) 
O(log n) 
1-jadval. Linear search va binary search algoritmi farqi 
Ko'rib turganingizdek, binary search algoritmi linear searchdan ko'ra muhim 
darajada tezroq ishlaydi, ammo ularning qidiruv zaxiralari, yani xotirani necha marta 
tekshirish kerakligi, bir xil bo'ladi. 


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. 

Download 292.43 Kb.

Do'stlaringiz bilan baham:
1   2




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