|
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.
\ (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.
Dostları ilə paylaş: |
