Mavzu: Algoritm murakabligini statik va dinamik o’lchovlari. Vaqt va xotira xajmi bo’yicha qiyinchiliklar

Algoritmga misollar
Bu erda oddiy algoritmlarning ba'zi misollari va ularning murakkabligini ko'rib chiqing.
Koʻrsatkich koʻtarish
Ushbu algoritm qadimgi Hindistonda bizning eramizdan oldin tasvirlangan va haqiqiy sonning \ (n \) tabiiy kuchini \ (x \) hisoblash uchun ishlatiladi.

1. 
   \ (n \) ni ikkilik tizimda yozing
   
2. 
   Ushbu yozuvdagi 1 ning har birini bir juft KX harfi bilan, har bir 0 ni esa K harfi bilan almashtiring
   
3. 
   Eng chapdagi KX juftligini kesib tashlang
   
4. 
   Olingan satrni chapdan o'ngga o'qish, K harfi bilan uchrashish, natijani kvadratga tushirish va X harfini uchratish, natijani x ga ko'paytiring. Boshida natija x ga teng.
   

Bu algoritmda biz ko'paytirish amallari soni ikkilik ko'rinishdagi raqamlar soniga eng yaxshi \ (n \) va eng yomoni \ (2 (n-1) \) ga teng. Vaqt murakkabligi baribir.
Algoritmni samarali amalga oshirishda qo'shimcha xotira amalda talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun fazoviy murakkablik \ (S (n) = \ matematik (O) (1) \) ga teng.
Shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Biroq, \ (\ mathcal (O) (n) \) ko'paytirish operatsiyalarini talab qiladigan "sodda" amalga oshirish bilan solishtirganda, bu algoritm nisbatan samarali.
Butun sonlarni ko‘paytirish
Ushbu ko'paytirish algoritmi ba'zan rus yoki dehqon deb ataladi, garchi u Qadimgi Misrda ham ma'lum bo'lgan.
Birinchi omil ketma-ket ikkiga ko'paytiriladi, ikkinchisi esa to'liq 2 ga bo'linadi. Natijalar ikkinchisi 1 bo'lguncha ikkita ustunga yoziladi.
Ko'paytirish natijasi birinchi ustundagi raqamlarning yig'indisi, ikkinchi ustundagi toq raqamlarning qarama-qarshiligi.
Butun sonlarni bo'lish va 2 ga ko'paytirishni siljish yo'li bilan bajarish mumkin bo'lganligi sababli, bu algoritm \ (2 \ log_2 n \) siljish amallarini beradi, bu erda \ (n \) ikkita sondan kichikroqdir. Eng yomon holatda, \ (\ log_2 n - 1 \) qo'shish operatsiyalari ham olinadi. Qanday bo'lmasin, vaqtning murakkabligi \ (T (n) = \ matematik (O) (\ log n) \).
Algoritmni samarali amalga oshirish uchun qo'shimcha xotira deyarli talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun \ (S (n) = \ mathcal (O) (1) \)
Yana shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Biroq, \ (\ mathcal (O) (n) \) qo'shish operatsiyalarini talab qiladigan "sodda" amalga oshirish bilan solishtirganda, bu algoritm nisbatan samaralidir.
Misol
23 ni 43 ga ko'paytiring.
Ikkinchi omil sifatida 23 ni olaylik.

43	23	g'alati
86	11	g'alati
172	5	g'alati
344	2
688	1	g'alati

Natija \ (43 + 86 + 172 + 688 = 989 \)
Bizda 10 ta smenali operatsiya va 4 ta qo'shimcha operatsiya mavjud. Malumot uchun, \ (\ log_2 (23) \ taxminan 4,52 \).
Algoritmning murakkabligini aniqlash
Asimptotik tahlilda olingan murakkablik funksiyasining bahosi algoritmning murakkabligi deyiladi.
Shuni yodda tutish kerakki, algoritmning murakkabligi bo'yicha bir nechta taxminlar mavjud.
Murakkablik funktsiyasining asimptotik xatti-harakati operatsion murakkablikdir. Unga qo'shimcha ravishda siz quyidagi qiyinchiliklar turlarini belgilashingiz mumkin.