Mavzu: Algoritmlar samaradorligini tahlil qilish. Reja: Samaradorlik ko’rsatkichlari

5. Algoritmlarni tahlil qilish ni topish jarayoni hisoblash murakkabligi algoritmlar - vaqt, saqlash yoki boshqa manbalar miqdori ularni ijro eting. Odatda, bu a ni o'z ichiga oladi funktsiya algoritm kiritish uzunligini va uni bajaradigan qadamlar soniga bog'laydigan (uning vaqtning murakkabligi) yoki u foydalanadigan saqlash joylari soni (uning kosmik murakkablik). Algoritm ushbu funktsiya qiymatlari kichik bo'lganda yoki kirish hajmining o'sishiga nisbatan sekin o'sganda samarali bo'ladi deyiladi. Xuddi shu uzunlikdagi turli xil yozuvlar algoritmning xatti-harakatlariga olib kelishi mumkin, shuning uchun eng yaxshi, eng yomon va o'rtacha ish tavsiflarning barchasi amaliy qiziqish uyg'otishi mumkin. Agar boshqacha ko'rsatilmagan bo'lsa, algoritmning ishlashini tavsiflovchi funktsiya odatda yuqori chegara, algoritmga eng yomon holatlardan aniqlandi.
"Algoritmlarni tahlil qilish" atamasi tomonidan kiritilgan Donald Knuth.^[1] Algoritmni tahlil qilish keng doiraning muhim qismidir hisoblash murakkabligi nazariyasi, bu berilganni hal qiladigan har qanday algoritm uchun zarur bo'lgan manbalar uchun nazariy baholarni beradi hisoblash muammosi. Ushbu taxminlar izlashning oqilona yo'nalishlari to'g'risida tushuncha beradi samarali algoritmlar.
Algoritmlarni nazariy tahlil qilishda ularning murakkabligini asimptotik ma'noda baholash, ya'ni o'zboshimchalik bilan katta kirish uchun murakkablik funktsiyasini baholash odatiy holdir. Big O notation, Katta-omega yozuvlari va Big-teta yozuvi shu maqsadda ishlatiladi. Masalan; misol uchun, ikkilik qidirish qidirilayotgan tartiblangan ro'yxat uzunligining logarifmiga mutanosib bo'lgan bir necha bosqichda yoki O (log (n)) da, so'zma-so'z " logaritmik vaqt". Odatda asimptotik taxminlar har xil bo'lgani uchun ishlatiladi amalga oshirish bir xil algoritm samaradorligi bilan farq qilishi mumkin. Ammo berilgan algoritmni istalgan ikkita "oqilona" amalga oshirish samaradorligi a deb nomlangan doimiy multiplikativ omil bilan bog'liq. yashirin doimiy.
Ba'zida samaradorlikning aniq (asimptotik bo'lmagan) o'lchovlari hisoblab chiqilishi mumkin, ammo ular odatda algoritmni amalga oshirishda ma'lum taxminlarni talab qiladi, deyiladi hisoblash modeli. Hisoblash modeli an nuqtai nazaridan aniqlanishi mumkin mavhum kompyutermasalan, Turing mashinasi, va / yoki ma'lum bir operatsiyalar birlik vaqtida bajarilishini e'lon qilish orqali, masalan, agar biz ikkilik qidiruv qo'llanadigan tartiblangan ro'yxatda n va biz ro'yxatdagi elementni har bir qidirishni birlik vaqtida, so'ngra eng ko'p jurnalda bajarilishi mumkinligiga kafolat beramiz₂ n Javobni qaytarish uchun + 1 marta birlik kerak.

Vaqt samaradorligini baholash biz qadam deb belgilagan narsaga bog'liq. Tahlilning haqiqiy bajarilish vaqtiga foydali bo'lishi uchun qadamni bajarish uchun zarur bo'lgan vaqt yuqorida doimiy bilan chegaralangan bo'lishi kafolatlanishi kerak. Bu erda ehtiyot bo'lish kerak; masalan, ba'zi tahlillar ikkita raqamning qo'shilishini bitta qadam deb hisoblaydi. Ushbu taxmin ba'zi kontekstlarda kafolatlanmasligi mumkin. Masalan, hisoblashda ishtirok etadigan raqamlar o'zboshimchalik bilan katta bo'lishi mumkin bo'lsa, bitta qo'shish uchun zarur bo'lgan vaqt endi doimiy deb qabul qilinmaydi.

Odatda ikkita iqtisodiy model qo'llaniladi:^{[2][3][4][5][6]}

• 
  
  The yagona xarajat modelideb nomlangan yagona narxlarni o'lchash (va shunga o'xshash farqlar), har bir mashinaning ishlashiga, ishtirok etadigan raqamlarning kattaligidan qat'i nazar, doimiy xarajatlarni belgilaydi
  
• 
  
  The logaritmik xarajatlar modelideb nomlangan logaritmik xarajatlarni o'lchash (va shunga o'xshash farqlar), har bir mashinaning ishlashiga sarflangan bitlar soniga mutanosib narx belgilaydi
  

Ikkinchisini ishlatish ancha noqulay, shuning uchun u faqat kerak bo'lganda, masalan, tahlil qilishda ishlaydi ixtiyoriy aniqlikdagi arifmetika ishlatiladigan algoritmlar kabi kriptografiya.

Tez-tez e'tibordan chetda qoladigan muhim nuqta shundaki, muammolar uchun nashr etilgan pastki chegaralar ko'pincha amalda ishlatishingiz mumkin bo'lgan operatsiyalar to'plamidan ko'ra cheklangan hisoblash modeli uchun beriladi va shuning uchun sodda bo'lganidan tezroq algoritmlar mavjud. mumkin deb o'yladim.^[7]