Algoritm haqda tushuncha

Algorithm Murakkabligi

Algoritmning murakkabligi (complexity) Space (joy) va Time (vaqt) miqdori asosida o’lchanadigan qiymat. Bunda Time dasturning ishlash jarayonida ketqizadigan vaqti; Space esa input, o’zgaruvchilar, output uchun kerak bo’ladigan joy miqdori. Bu ikki faktor algoritmni effektivligini aniqlaydi. Yaxshi algoritmlarda Space va Time kam miqdorda bo’ladi, bu esa usha algoritmda yozilgan kodning ishlash tezligini, performanceni oshiradi.
Endi savol tug’ilishi mumkin, nimaga oddiy bir masalani yechish uchun algoritmining effektivligi haqida qayg’urishimiz kerak? Yoki dasturlash jarayonida frameworklardan foydalanganda ham performance haqida o’ylash kerakmi?
Ko’p hollarda katta proyektlarda millionlab qator ma’lumotlar ustida amallar bajarishga to’g’ri keladi. Shunda kichik masalalarda sezilmagan kodning performance muammosi, katta hajmdagi ma’lumotlarni qayta ishlashda yaqqol ko’rinadi. Performance muammosi kodning ishlash tezligiga ta’sir qiladi, ishlashda xotiradan ko’proq joy egallashiga olib keladi.
Asl maqsad tech giant korporatsiyalarga ishga kirish ekan, performance’ni birinchi o’ringa qo’yish, yozilgan kodni tahlil qilib, complexity’ni aniqlay olish kerak bo’ladi.
Yaqinda o’zimizda bo’lib o’tgan performance muammosi haqida:
Backendni optimizatsiya qilish jarayonida bir millionga yaqin foydalanuvchi ma’lumotlarini yig’ib, bazada bir jadvalga saqlash kerak bo’lib qoldi. Frameworkning tayyor funksiyalari yordamida yozilgan kod, ishni tugatish uchun 5 soatdan ko’p vaqt olishi ma’lum bo’ldi. Turgan gapki, shuncha foydalanuvchisi bor saytni 5 soat o’chirib qo’yolmaymiz. Keyin kodni optimizatsiya qilib, frameworkni ishlatmasdan yozib chiqqanimda 40 minutda import qiladigan bo’ldi.
Algoritmlarni tahlil qilishni yana Asymptotic analysis ham deyiladi. Bunda kiritilgan input kattaligiga qarab algoritmning ishlash vaqti hisoblanadi.
Asymptotic analysis ga misol sifatida tartiblangan array’dan berilgan X sonni topish uchun Linear Search va Binary Search algoritmlarini taqqoslaymiz.
Linear search siklda arrayning birinchi elementidan boshlab X ni topguncha array elementlarini bittalab tekshirib chiqadi. Array uzunligini N deb oladigan bo’lsak, X ni topish uchun minimal 1 maksimal, N solishtirishni amalga oshiradi.
Binary search array’ning o’rtasidagi element qiymatini – M ni oladi va uni X bilan solishtiradi:

• 
  X M ga teng bo’lsa, bingo! birinchi urinishdayoq kerakli element topildi.
  
• 
  Agar X M dan kichik bo’lsa, demak qidirishni arrayning birinchi yarmidan davom ettirish kerak.
  
• 
  Agar X M dan katta bo’lsa, demak qidirishni arrayning ikkinchi yarmidan davom ettiriladi.
  

Hudi shunday uslubda, avval qismning o’rtasi M topiladi, keyin X ni M bilan solishtirib boriladi.
Bunda minimal urinish 1, maksimal urinish log N marta bo’ladi. Ya’ni array uzunligi 10 ta bo’lsa binary searchda maksimum 3 ta urinishda X ni topish mumkin. Linear searchda esa maksimum 10ta urinish bo’lgan bo’lardi. Endi 100,000 elementi bor katta arrayni oladigan bo’lsak:

• 
  Linear searchda max 100,000 urinish
  
• 
  Binary searchda max 16 urinish!
  

Har bir urinishni shartli ravishda 1 sekund deb hisoblaganda, linear search 27,78 soatda ishni tugatadi. Binary search 16 sekundda. Demak, ikki algoritmni solishtirganda eng yomon holatda (worst case) binary search 6250 marta tez ishlaydi.
Kerakli tanlangan algoritm dasturning ishlash tezligini oshiradi. Katta loyihalarda bo’lsa mablag’ tejalishiga olib keladi.
Biz aytib o’tgan urinishlar sonini aniqlashda ko’pincha best case, average case va worst case hisoblanadi.
Linear searchda va binary search’da best case 1.
Best case’ning yana bir nomi lower bound.
Worst case’niki – upper bound.
Lower bound va upper bound grekcha Θ harfi bilan yoziladi.
Linear search va binary search algoritmlari Θ da yozilganda:
Best case:
– linear search – Θ(1)
– binary search – Θ(1)
Worst case:
– linear search – Θ(n)
– binary search – Θ(log n)
Ba’zi algoritmlarda lower bound va upper bound bir xil bo’ladi, bu degani algoritm input kattaligidan qat’iy nazar, bir xil amalni bajaradi. Bunga misol qilib MergeSort ni keltirish mumkin. MergeSort‘da upper va lower bound bir xil – Θ(n log n).