Algaritmlash va Loihalash fanidan

Algoritmlarning asimptotik tahlili

• Amallarning sonini sanash juda mayda ish, eng muhimi bu unchalik muhim emas. Yuqorida keltirilgan qoidalardan kelib chiqqan holda, algoritmning murakkabligini aniqlashda oldin bajarganimizdek amallarni sanash kerak emas, biz uchun algoritm (operator yoki operatorlar guruhi) konstruksiyasi qaysi murakkablik darajasiga mansubligini bilish kifoya. Bundan ma’lumki, sikl va rekursiyalarga ega bo’lmagan algoritm O(1) konstanta murakkabligiga ega. n ta iteratsiyani bajaruvchi siklning murakkabligi O(n) ga teng. Bitta n o’zgaruvchi qiymatiga bog’liq bo’lgan ichma ich joylashgan ikkita siklning konstruksiyasi kvadratik murakkablikka O(n2) ega bo’ladi.
• Quyida eng ko’p uchraydigan murakkablik sinflari keltirilgan:
• O(1) – konstantali murakkablik;
• О(n) – chiziqli murakkablik;
• О(nа) – polynomial murakkablik;
• О(log(n)) – logarifmik murakkablik;
• O(n*log(n)) – kvazichiziqli murakkablik;
• O(2n) – eksponensial murakkablik;
• O(n!) –factorial murakkablik.

Saralash algoritmlari

• Saralash algoritmlari – informatikada juda yaxshi o’rganilgan sohalardan biri va u juda keng qamrovli qo’llanilish sohasiga ega. Ularni katta hajmdagi ma’lumotlarni saqlash va qayta ishlash amallari bajariladigan har qanday joyda uchratish mimkin. Ba’zi ma’lumotlarni qayta ishlash masalalari agar ma’lumotlar saralangan bo’lsa oson yechiladi. Bunday masalalar ushbu laboratoriya ishida ko’rib chiqiladi.
• Saralash metodlari
• Odatda saralash metodlarini ikkiga ajratishadi:
• Ichki saralash –ma’lumotlar operativ xotirada joylashgan bo’lib, bunda dasturning harakatlari sonini (solishtirish, solishtirishlar soni, elementlar almashinuvi va b.qa metodlarga asoslangan) optimallashtirish muhim ahamiyat kasb etadi;
• Tashqi saralash – ma’lumotlar murojaatlarni sekinlashtiruvchi tashqi hotirada (magnit lenta, baraban, disk va b.qa) joylashgan bo’lib, bunda aynan shu qurilmaga murojaatlar sonini kamaytirish lozim.
• Bu labaratoriya ishida ko’plab dasturchilar uchun amaliyotda muhim bo’lgan massiv elementlarini ichki saralash algoritmlarini ko’rib chiqamiz.
• Ta’kidlash joizki, surish orqali saralash algoritmini tashqi ma’lumotlarni saralashda qo’llash ham qulay.