Algoritm — muammoni yechish yoki ma’lum natijani olish uchun bajariladigan aniq va chekli amallar ketma-ketligi. Algoritm dasturlash tiliga bog‘liq emas: u tabiiy til, psevdokod, blok-sxema yoki matematik ifoda bilan tasvirlanishi mumkin. Dastur esa algoritmning kompyuter bajara oladigan tildagi amalga oshirilishidir.
Asosiy xususiyatlari
Algoritmning har bir qadami tushunarli va bir ma’noli bo‘lishi kerak. Bir xil kirish va bir xil boshlang‘ich holat deterministik algoritmda bir xil natija beradi. Algoritm chekli qadamdan keyin to‘xtashi, ruxsat etilgan kirishlar uchun natija hosil qilishi va bajarilishi mumkin bo‘lgan amallardan tuzilishi talab etiladi.
Har bir masala uchun bitta algoritm mavjud bo‘lishi shart emas. Masalan, ro‘yxatni saralash insertion sort, merge sort, heap sort yoki quicksort bilan bajarilishi mumkin. Ular natijada tartiblangan ro‘yxat beradi, ammo xotira sarfi, bajarilish vaqti va eng yomon holatdagi xatti-harakati bilan farq qiladi.
Murakkablik
Algoritm samaradorligi kirish hajmi oshganda bajariladigan amallar va qo‘shimcha xotira qanday o‘sishi bilan baholanadi. Time complexity vaqt o‘sishini, space complexity xotira talabini ifodalaydi. Big O yozuvi yuqori chegarani tasvirlashda ishlatiladi. Masalan, binary search saralangan massivda qidiruv maydonini har qadamda yarmiga kamaytirib, O(log n) vaqt talab qiladi.
Murakkablik real sekundni bevosita bermaydi. Protsessor, dasturlash tili, ma’lumot joylashuvi va implementatsiya konstantalari amaliy vaqtga ta’sir qiladi. Shunga qaramay, O(n²) algoritm katta kirishda O(n log n) algoritmdan odatda tezroq o‘sadi. Average-case, worst-case va amortized tahlil turli ish sharoitlarini ko‘rsatadi.
Algoritm turlari
Divide and conquer masalani kichik qismlarga bo‘ladi, ularni yechib, natijalarni birlashtiradi. Merge sort bunga misol. Greedy algoritm har bosqichda lokal eng yaxshi tanlovni qiladi; bu usul faqat masala xususiyatlari lokal tanlov global yechim berishini kafolatlaganda to‘g‘ri ishlaydi.
Dynamic programming takrorlanadigan kichik masalalar natijasini saqlaydi. Backtracking nomzod yechimni bosqichma-bosqich quradi va shart buzilganda oldingi holatga qaytadi. Randomized algoritm ayrim qarorlarda tasodifiy qiymatdan foydalanadi. Parallel algoritm hisobni bir nechta bajaruvchi o‘rtasida taqsimlaydi.
To‘g‘rilik
Algoritmning misollarda ishlashi uning barcha ruxsat etilgan kirishlar uchun to‘g‘riligini isbotlamaydi. Loop invariant siklning har iteratsiyasida saqlanadigan xususiyatni ifodalaydi. Induksiya va formal isbot algoritm natijasining spetsifikatsiyaga mosligini ko‘rsatishi mumkin. Amaliy dasturda esa unit test, property-based test va chegaraviy qiymatlar implementatsiyadagi xatolarni topishga yordam beradi.
Barqarorlik va kirish sharti
Saralash algoritmi stable bo‘lsa, kaliti teng elementlarning oldingi nisbiy tartibini saqlaydi. Bu yozuvlar avval sana, keyin kategoriya bo‘yicha saralanganda muhim bo‘lishi mumkin. In-place algoritm esa kirishdan tashqari juda kam qo‘shimcha xotira ishlatadi. Stable va in-place xususiyatlari bir-biridan mustaqil.
Algoritmning preconditioni ishlashdan oldin bajarilishi kerak bo‘lgan shartdir. Binary search uchun massiv saralangan bo‘lishi shunday shart. Postcondition bajarilgandan keyingi kafolatni ifodalaydi. Shartlar hujjatda aniq yozilmasa, to‘g‘ri algoritm noto‘g‘ri kirishda xato natija berishi mumkin.
Bog‘liq tushunchalar
Ma’lumotlar tuzilmasi, Big O, psevdokod, murakkablik, rekursiya, saralash, qidiruv