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


Pastki chegara ekanligini ko'rsatish mumkin



Download 101,89 Kb.
bet10/19
Sana14.06.2022
Hajmi101,89 Kb.
#672007
1   ...   6   7   8   9   10   11   12   13   ...   19
Bog'liq
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

Pastki chegara ekanligini ko'rsatish mumkin
3 n2 –100 n+6 ¹ V(n3 ) da C = 1.
Tengsizlik 3 n2 –100 n+6 ³ n3 bajarilmagan.
3 n2 –100 n+6= V(n)
C1 = , n> n0 .
https://pandia.ru/text/78/183/images/image007_89.gif "kenglik =" 305 "balandlik =" 247 src = ">
f1 (N)=100 n2
f2 (N)=5 n3
n0 =20 – tanqidiy nuqta.
Murakkablik darajasi pastroq bo'lgan algoritmlarga ustunlik berishning yana bir sababi shundaki, murakkablik tartibi qanchalik past bo'lsa, masalaning hajmi shunchalik katta bo'ladi. N amaliy jihatdan hal qilish mumkin.
0 "style =" margin-left: 5,4pt; chegarani yig'ish: yig'ish; chegara: yo'q ">
n!
6-misol:
Shuni yodda tutish kerakki, algoritmlarning murakkabligi o'sishining katta tartibi, qoida tariqasida, kichikroq konstantaga ega. C1 doimiy bilan xarakterlanadi murakkabligi o'sish kichik tartibi bilan solishtirganda C2.
Bunday holda, kichik hajmdagi muammolarni hal qilish uchun tez o'sib borayotgan murakkablikdagi algoritm afzalroq bo'lishi mumkin ( n® 0 ).
Xuddi shu muammoni hal qilishda qiyinchiliklarga duch keladigan beshta algoritm berilsin:
A1: 100 N
A2: 100 N* logN
A3: 10 N2
A4: N3
A5: 2 N
Keyin, bilan bog'liq muammolar uchun N=2 ¸ 9 tezroq A5 bo'ladi ( f(N) ~ 4 ¸ 512 ). Boshqa algoritmlar, almashtirilganda, sezilarli darajada pastroq stavkalarni beradi.
Da N=10 ¸ 58 A3 ga afzallik beriladi.
Da N=59 ¸ 1024 eng samarali A2 bo'ladi.
Da N>1024 A1 ga afzallik beriladi.
Bir nechta ketma-ket yoki bir vaqtda bajariladigan algoritmlardan tashkil topgan dasturlar uchun murakkablik quyidagicha baholanadi: summa qoidasi va ishlar qoidasi.
Jamlama qoidasi : Dastur ikkita ketma-ket bajariladigan R1 va R2 algoritmlaridan iborat bo'lsin, ular uchun qiyinchiliklar aniqlanadi. O(f(n)) va O(g(n)) mos ravishda. Keyin butun dasturning vaqt murakkabligi algoritmlarning har birining vaqt murakkabligi yig'indisi sifatida aniqlanadi:
T(n) = T1 (n)+ T2 (n)
Umuman olganda, biz quyidagilarni olamiz:
T (n)Þ O (maksimal f (n), g (n))
Ishlar qoidasi: Murakkablik tartibi bilan ikkita parallel bajaruvchi algoritmdan tashkil topgan dasturning vaqt murakkabligi bo'lsin. O(f(n)) va O(g(n)) Shunga ko'ra, u algoritmlarning har birining vaqt murakkabligi mahsuloti sifatida aniqlanadi:
T(n) = T1 (n)* T2 (n)
Umuman:
T(n) Þ O(f(n)* g(n))

Download 101,89 Kb.

Do'stlaringiz bilan baham:
1   ...   6   7   8   9   10   11   12   13   ...   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