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


Download 305.73 Kb.
bet17/19
Sana18.06.2023
Hajmi305.73 Kb.
#1573762
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 305.73 Kb.

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




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