20.1 Elementar berilganlar strukturasi Berilganlar strukturasi.
Berilganlar strukturasi bu EHMning dasturiy birligi bo’lib,u xotira yacheykasiga yozish, ma’lumotlarni bir xil tipda saqlash usullari to’plamidir.
Bundan ko’rinadiki, berilganlar strukturasi EHM xotirasida kerakli ma’lumotlar to’plamini saqlashga xizmat qiladi. Bunday strukturaning ajralmas qismlaridan biri strukturada saqlanuvchi ma’lumotlarni samarali boshqarishni ta’minlovchi amallar to’plamidir. Bunday amallarga saqlangan ma’lumotlarni o’qish va yozish amallari misol bo’la oladi. Bunday amallar odatda, EHM darajasidan kelib chiqqan holda realizatsiya qilinadi. Shuning uchun bundan keyin uning mehnat hajmi(трудомкость) O(1) deb faraz qilamiz.
Elementar berilganlar strukturasi.
Elementar berilganlar strukturasi shunday berilganlar strukturasiki, ularni EHMning ixtiyoriy bazaviy strukturalari deb atash mumkin. Shulardan massiv va bog’langan ro’yxat bilan tanishamiz.Shuni ta’kidlash lozimki, ularni avtomarniy berilganlar strukturasi deb atash mumkin, chunki, ularni modellashtirishda boshqa elementar berilganlar strukturasidan foydalanilmaydi.
22.1 Rekursiya. Rekursiv algoritmlar Rekursiya haqida tushuncha.
Izoh
Rekursiya (umuman) – bu ob’ektni mazkur ob’ektga murojat qilish orqali aniqlashdir.
Izoh
Rekursiv algoritm – bu algoritmi aniqlashda o’ziga bevosita yoki bilvosita murojat qilishdir.
Eslatma: Algoritm va dasturlarni tuzishda rekursiyadan foydalanish vaqtni tejaydi, hajmi kichi bo’ladi, lekin interaksion usulga isbatan dastur sekinroq ishlaydi hamda ko’proq hotira talab qiladi.
Def.1.
Agar ma’lumotlar tuzilmasi elementlari ham mazkur tuzilmaga o’xshash tuzilma bo’lsa , u holda bunday tuzilmaga rekursiv ma’lumotlar tuzilmasi deyiladi.
Rekursiv ob’ektlarga misollar.
Serpinskiy uchburchagi.
Rekursiv triada.
Parametrizatsiya qilish – masala shartini tasniflash va uni hal etish uchun parametrlar aniqlanadi;
Rekursiya bazasi (asosi) – masala yechimi aniq bo’lgan trivial holat aniqlanadi, ya’ni bu holatda funksiyani o’ziga murjat qilishi talab etilmadi.;
Dekompozitsiya – umumiy holatni nisbatan ancha oddiy bo’lgan o’zgargan parametrli qisim masalalar orqali ifodalaydi.
Izoh
Rekursiv yoki interatsion usul samaradorligi berilgan masalani hal qiluvchi dasturni turli boshlang’ich qiymatlarda tahlil etish orqali aniqlaydi.
Izoh
Rekursiv algoritmlarni samaradorligini oshirish ko’pincha triada bosqichlarini qayta ko’rib chiqish natijasida amalga oshirish mumin.
22.2 Merge sort Birlashtirish tartibi - har bir kichik roʻyxat bitta elementdan iborat boʻlgunga qadar roʻyxatni bir nechta kichik roʻyxatlarga boʻlish va saralangan roʻyxat hosil qiladigan tarzda oʻsha quyi roʻyxatlarni birlashtirish gʻoyasiga asoslangan boʻlish va boʻysundirish algoritmi.
G'oya:
Saralanmagan ro'yxatni har bir elementni o'z ichiga olgan pastki ro'yxatlarga bo'ling.
Ikkita yagona ro'yxatning qo'shni juftlarini oling va 2 ta element ro'yxatini yaratish uchun ularni birlashtiring. endi 2 o'lchamdagi ro'yxatlarga aylanadi.
Olinganlarning yagona tartiblangan ro'yxatiga qadar jarayonni takrorlang.
Birlashtirish uchun ikkita pastki ro'yxatni taqqoslashda ikkala ro'yxatning birinchi elementi hisobga olinadi. O'sish tartibida tartiblanganda, qiymati kichikroq bo'lgan element tartiblangan ro'yxatning yangi elementiga aylanadi. Ushbu protsedura ikkala kichik pastki ro'yxat bo'sh bo'lguncha va yangi birlashtirilgan pastki ro'yxat ikkala pastki ro'yxatning barcha elementlarini o'z ichiga olguncha takrorlanadi.
