1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar



Download 101,89 Kb.
bet17/19
Sana14.06.2022
Hajmi101,89 Kb.
#672007
1   ...   11   12   13   14   15   16   17   18   19
Bog'liq
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

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.

Download 101,89 Kb.

Do'stlaringiz bilan baham:
1   ...   11   12   13   14   15   16   17   18   19




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish