Mavzu: Algoritm murakabligini statik va dinamik o’lchovlari. Vaqt va xotira xajmi bo’yicha qiyinchiliklar

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))