“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Algoritm tartibi – chiziqli hisoblanadi - O(N) belgilanadi.

Binar qidiruv algoritmi

Сmin = 1, Cmax = log2(N)

Algoritm tartibi – logarifmik hisoblanadi – O(logN) belgilanadi.

O’tish qidiruv algoritmi

p – qadam o’lchovi

Сmin = 1+1, Cmax = √n + √n

Algoritm tartibi - O(√n) belgilanadi.

Chiziqli qiduruvni Mukamallashtirish usullari

• Topilgan elementni jadval boshiga qoʼyish orqali jadvalni qayta tartiblash;
• Transpozitsiya usuli.

Birinchi usulni magʼzi shundan iboratki, berilgan kalitga teng kalitli element jadvalda birinchi element deb oʼzlashtiriladi, qolganlari esa suriladi.
Keltirilgan algoritm roʼyxat uchun ham massiv uchun xam oʼrinli. Biroq bu algoritm massiv uchun tavsiya qilinmaydi, sababi elementlarni oʼrinlashtirishga koʼrsatkichlarni oʼrinlashtirishdan koʼra ancha koʼp vaqt talab qiladi.
Transpozitsiya usulida topilgan element jadvalda bitta oldingi element bilan oʼrin almashtiriladi. Аgarda mazkur elementga koʼp murojaat qilinsa, bittadan oldinga surilib borib natijada jadval boshida boʼladi.
Ushbu usul nafaqat roʼyxatda, balki massivda xam qulay (sababi faqatgina ikkita yonma-yon turgan element oʼrin almashtiriladi).

Саралаш алгоритмларини тадқиқ қилиш

Режа:

• Саралаш тушунчаси ва вазифаси;
• Саралаш усулларининг классификацияси;
• Саралаш масаласининг формал қўйилиши;
• Саралашнинг қатъий усуллари.

Мавзу: Саралашнинг қатъий усуллари

Саралаш тушунчаси ва унинг вазифаси

Саралашдан мақсад - тартибланган тўпламда керакли элементни топишни осонлаштиришдан иборат.

Изоҳ
Саралаш – бу берилган тўплам элементларини бирор бир тартибда (ўсиш ёки камайиш) жойлаштириш жараёнидир.

• дастурларни трансляция қилишда;
• маълумотлар мажмуасини ташқи хотирада ташкил қилишда;
• кутубхоналар, каталоглар, маълумотлар базасини яратишда ва бошқ.