1-§. Ma’lumotlar turlari va algoritmlari. Ma’lumotlarning abstrakt tuzilmalari

Murakkablikni baholash. Algoritmlarning murakkabligi odatda bajarilish vaqti yoki ishlatilgan xotira boʻyicha baholanadi. Ikkala holatda ham, murakkablik kiritilgan ma‘lumotlarning hajmiga bogʻliq: 100 ta elementdan iborat massivi xuddi shunga oʻxshash 1000 ta elementdan iborat massivga qaraganda tezroq qayta ishlanadi. Shu bilan birga, aniq vaqt bilan bir necha kishi qiziqadi: bu protsessorga bogʻliq, ma‘lumotlar turi, dasturlash tili va boshqa koʻplab parametrlarga ham bogʻliq. Faqatgina asimptotik murakkablik muhim, ya‘ni kirish ma‘lumotlarining kattaligi cheksizlikka intilayotgandagi murakkablik.
Masalan, ba‘zi bir algoritmga kirish ma‘lumotlarining n ta elementlarini qayta ishlash uchun 2n³ + 6n ta shartli amallarni bajarish kerak. n ning ortishi bilan ishning umumiy davomiyligi n ning kubi uni 2 ga koʻpaytirgandan yoki 6n ni qoʻshgandan koʻra koʻproq ta‘sir qiladi. Ushbu algoritmning vaqt murakkabligi O(n³), ya‘ni u kubik bilan kiritilgan ma‘lumotlarning hajmiga bogʻliq boʻladi.
Bosh harf O dan foydalanish matematikadan kelib chiqadi, bu yerda ushbu belgi funksiyalarning asimptotik harakatlarini taqqoslash uchun ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki egallagan xotira miqdori), kiritilgan ma‘lumotlarning hajmiga qarab, f(n) ga koʻpaytiriladigan ba‘zi konstantalardan tezroq emasligini anglatadi.
O(n) - chiziqli murakkablik. Bunday murakkablik, masalan, saralanmagan massivdagi eng katta elementni topish algoritmiga ega. Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n elementlaridan oʻtishimiz kerak boʻladi.
O(log n) - logaritmik murakkablik. Eng oddiy misol - ikkilik qidirish. Agar massiv saralangan boʻlsa, uni yarmiga boʻlish orqali ma‘lum bir qiymatga ega ekanligini tekshirishimiz mumkin. Oʻrta elementni tekshirib koʻramiz, agar u kattaroq boʻlsa, unda massivning ikkinchi yarmini tashlab yuboramiz. Agar kichikroq boʻlsa, unda aksincha - biz dastlabki yarmini tashlaymiz va shu tarzda ikkiga boʻlinishni davom ettiramiz, natijada (logn) elementlarini tekshiramiz.
O(n²) - kvadratik murakkablik. Bunday murakkablik, masalan, element qoʻshilishi natijasida yangi saralash algoritmiga ega. Kanonik dasturda bu ikkita ichki sikldan iborat: biri butun massivni bosib oʻtish, ikkinchisi esa allaqachon ajratilgan qismdan keyingi element uchun joy topish. Shunday qilib, amallar soni n*n, ya‘ni n² kabi massiv oʻlchamiga bogʻliq boʻladi.
Murakkablikning boshqa koʻrinishlari ham mavjud, ammo ularning barchasi bir xil prinsipga asoslanadi.
Algoritmning ishlash vaqti umuman kiritilgan ma‘lumotlarning hajmiga bogʻliq emasligi ham sodir boʻladi. Bu holda murakkablik O(1) bilan belgilanadi. Masalan, massivning uchinchi elementi qiymatini aniqlash uchun elementlarni eslab qolishingiz yoki ular orqali bir necha bor oʻtishingiz shart emas. Siz har doim ma‘lumotlarni kiritish oqimidagi uchinchi elementni kutishingiz kerak va bu esa siz uchun natija boʻladi, bu har qanday ma‘lumot uchun hisoblash uchun bir xil vaqtni oladi.
Baholash muhim boʻlgan taqdirda xotiradan xuddi shu tarzda amalga oshiriladi. Biroq, algoritmlar kirish ma‘lumotlarining hajmi boshqalarga nisbatan kattalashganda sezilarli darajada koʻproq xotiradan foydalanishi mumkin, ammo ular tezroq ishlaydi va aksincha. Bu hozirgi sharoit va talablar asosida muammolarni hal qilishning eng yaxshi usullarini tanlashga yordam beradi.