|
Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari Doimiy vaqt
|
| bet | 17/19 | | Sana | 14.05.2024 | | Hajmi | 78,19 Kb. | | #230972 |
Bog'liq Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va x-fayllar.orgAlgoritmga 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.
\ (n \) ni ikkilik tizimda yozing
Ushbu yozuvdagi 1 ning har birini bir juft KX harfi bilan, har bir 0 ni esa K harfi bilan almashtiring
Eng chapdagi KX juftligini kesib tashlang
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.
|
| |
