WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Algoritm va algoritm murakkabligi

Algoritm va algoritm murakkabligi

Algoritm deb hisoblaş yoki masalani yeçiş jarayonlarining ketma-ketligi yiğindisi tuşuniladi. Algoritmlar biror dasturlaş tiliga boğliq bölmaydi, ular istalgan tilda kod yozilgan taqdirda ham bir xil natijaga olib keladigan instruksiyalardir.

Ammo barça instruksiyalar ham algoritm bölavermaydi. Algoritm bölişi uçun, instruksiya bir neça xarakteristikalarga ega böladi:

  • Barça qadamlar aniq körsatilgan bölişi kerak
  • Input va Output turi aniq belgilangan bölişi kerak
  • Çegarali. Algoritm doimiy siklga tuşib qolmasligi, ohirgi qadamlarigaça yetib borişi zarur
  • Oson. Algoritm istalgan dasturlaş tilida amalga oşiriş mumkin böladigan darajada oson tuziladi

Algorithm Murakkabligi

Algoritmning murakkabligi (complexity) Space (joy) va Time (vaqt) miqdori asosida ölçanadigan qiymat. Bunda Time dasturning işlaş jarayonida ketqizadigan vaqti; Space esa input, özgaruvçilar, output uçun kerak böladigan joy miqdori. Bu ikki faktor algoritmni effektivligini aniqlaydi. Yaxşi algoritmlarda Space va Time kam miqdorda böladi, bu esa uşa algoritmda yozilgan kodning işlaş tezligini, performanceni oşiradi.

Endi savol tuğilişi mumkin, nimaga oddiy bir masalani yeçiş uçun algoritmining effektivligi haqida qayğurişimiz kerak? Yoki dasturlaş jarayonida frameworklardan foydalanganda ham performance haqida öylaş kerakmi?

Köp hollarda katta proyektlarda millionlab qator ma'lumotlar ustida amallar bajarişga töğri keladi. Şunda kiçik masalalarda sezilmagan kodning performance muammosi, katta hajmdagi ma'lumotlarni qayta işlaşda yaqqol körinadi. Performance muammosi kodning işlaş tezligiga ta'sir qiladi, işlaşda xotiradan köproq joy egallaşiga olib keladi.

Asl maqsad tech giant korporatsiyalarga işga kiriş ekan, performance'ni birinçi öringa qöyiş, yozilgan kodni tahlil qilib, complexity'ni aniqlay oliş kerak böladi.

Yaqinda özimizda bölib ötgan performance muammosi haqida:
Backendni optimizatsiya qiliş jarayonida bir millionga yaqin foydalanuvçi ma'lumotlarini yiğib, bazada bir jadvalga saqlaş kerak bölib qoldi. Frameworkning tayyor funksiyalari yordamida yozilgan kod, işni tugatiş uçun 5 soatdan köp vaqt olişi ma'lum böldi. Turgan gapki, şunça foydalanuvçisi bor saytni 5 soat öçirib qöyolmaymiz. Keyin kodni optimizatsiya qilib, frameworkni işlatmasdan yozib çiqqanimda 40 minutda import qiladigan böldi.

Algoritmlarni tahlil qilişni yana **Asymptotic analysis **ham deyiladi. Bunda kiritilgan input kattaligiga qarab algoritmning işlaş vaqti hisoblanadi.

Asymptotic analysis ga misol sifatida tartiblangan array'dan berilgan X sonni topiş uçun Linear Search va Binary Search algoritmlarini taqqoslaymiz.

Linear search siklda arrayning birinçi elementidan boşlab X ni topgunça array elementlarini bittalab tekşirib çiqadi. Array uzunligini N deb oladigan bölsak, X ni topiş uçun minimal 1 maksimal, N soliştirişni amalga oşiradi.

Binary search array'ning örtasidagi element qiymatini - M ni oladi va uni X bilan soliştiradi:

  • X M ga teng bölsa, bingo! birinçi urinişdayoq kerakli element topildi.
  • Agar X M dan kiçik bölsa, demak qidirişni arrayning birinçi yarmidan davom ettiriş kerak.
  • Agar X M dan katta bölsa, demak qidirişni arrayning ikkinçi yarmidan davom ettiriladi.

Hudi şunday uslubda, avval qismning örtasi M topiladi, keyin X ni M bilan soliştirib boriladi.

Bunda minimal uriniş 1, maksimal uriniş log N marta böladi. Ya'ni array uzunligi 10 ta bölsa binary searchda maksimum 3 ta urinişda X ni topiş mumkin. Linear searchda esa maksimum 10ta uriniş bölgan bölardi. Endi 100,000 elementi bor katta arrayni oladigan bölsak:

  • Linear searchda max 100,000 uriniş
  • Binary searchda max 16 uriniş!

Har bir urinişni şartli ravişda 1 sekund deb hisoblaganda, linear search 27,78 soatda işni tugatadi. Binary search 16 sekundda. Demak, ikki algoritmni soliştirganda eng yomon holatda (worst case) binary search 6250 marta tez işlaydi.

Kerakli tanlangan algoritm dasturning işlaş tezligini oşiradi. Katta loyihalarda bölsa mablağ tejalişiga olib keladi.

Biz aytib ötgan urinişlar sonini aniqlaşda köpinça 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 grekça Θ 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 böladi, bu degani algoritm input kattaligidan qat'iy nazar, bir xil amalni bajaradi. Bunga misol qilib MergeSort ni keltiriş mumkin. MergeSort'da upper va lower bound bir xil - Θ(n log n).