Izlash masalasi uchun algoritmlar va ularning murakkabligini aniqlash. Chiziqli qidiruv. - Aytaylik bizga massiv berilgan:
- A={1,2,3,4,5,6,7,8,9,10}
- Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan algoritm tuzish sharti qo'yilgan.
- Ushbu masalani yechishda eng birinchi hayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
- Chiziqli qidiruv - Linear Search deb ataladi, va bu usul algoritmi quyidagi ko'rinishda:
Blok-sxemasi:
Boshlash
N,A[N], X
i=1,..,N
A[i]≠X
1:Tamom
Yo’q
1
+
-
Bor
Binar(ikkilik) qidiruv. - Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.
- Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:
- funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish(kamayish) tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
- chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n).
Blok-sxemasi:
Boshlash
N,A[N], X
(i<=j) and not f
Tamom
f
+
-
i=1,j=N,f=false
m=(i+j) div 2
A[m]=X
f=true
A[m]
i=m+1
J=m-1
+
-
+
-
Blok-sxemasi(boshqa ko’rinishi)
Do'stlaringiz bilan baham: |
