Mavzu : Algoritm murakkabligini statik va dinamik o’lchovlari. Vaqt va xotira hajmi bo’yicha qiyinchiliklar reja

2.2 Ova Ō - belgilar.
Vaqt murakkabligining xulq-atvorining tabiati ortib borayotganida N (N® ¥ ) chaqirdi algoritmning asimptotik murakkabligi.
Asimptotik murakkablikning o'sish tezligini tavsiflash uchun biz foydalanamiz O-notatsiyasi. Algoritmning vaqt murakkabligi tartibida deyilganda N2 :
T(N)= O(N2 )= O(f(N)),
Keyin musbat konstantalar borligi taxmin qilinadi C, n0 =const (C>0), hamma uchun shunday N ³ N0 tengsizlik amal qiladi
T(N) £ C* f(N)
Bu murakkablik bahosining yuqori chegarasi.
2-misol:
Mayli T (0) = 1, T (1) = 4, ..., T (N)=(N+1) 2, keyin bu algoritmning vaqt murakkabligi o'sish tartibida bo'ladi T(N)= O(N2 ).
Buni hamma uchun ko'rsatish mumkin N > n0 da n0 = 1, C = 4 tengsizlik (1) bajariladi.
(N+1)2 £ 4* N2
3-misol:
Vaqt murakkabligi polinom sifatida yozilsa
T(N)= C1 N2 + C2 N+ C3 ,
u holda bunday algoritm polinomning maksimal elementi darajasiga karrali murakkablik tartibiga ega, chunki u eng tez o'sadi. N® ¥ :
T(N)= O(N2 ).
Masalan:
3 n2 +5 n+1 £ 5 n2
" n ³ 1
4-misol:
Agar ba'zi bir algoritm bir nechta murakkablikka ega bo'lsa 3 n, u holda tezlikning o'sish tartibi ko'paytmali bo'lishi mumkin emasligini ko'rsatish mumkin O(2 n):
T(N)=3 n¹ O(2 n).
Doimiylar bo'lsin C, n0 , shunday qilib, quyidagi tengsizlik amal qiladi:
3n £ C*2 n, n > n0 .
Bu erdan biz olamiz:
BILAN³ (3/2)2, n > n0 .
Lekin bilan n® ¥ bunday doimiy mavjud emas BILAN bu tengsizlikni qondiradi.
Murakkablikning yuqori chegarasidan tashqari, vaqtinchalik murakkablikning o'sish tezligining pastki chegarasi ham mavjud:
T(N) ³ V(f(N))
Tengsizlik (2) qandaydir doimiy borligini bildiradi BILAN buning uchun N® ¥ vaqt murakkabligi
T(N) ³ C* f(N).
T (N) (asimptotik vaqt murakkabligi) ni aniq aniqlashning murakkabligini hisobga olgan holda, dastlabki ma'lumotlarning hajmiga qarab, amalda algoritmning vaqt murakkabligining pastki va yuqori chegaralari qo'llaniladi:


T(N) = q (f(N))
Konstantaning qiymatiga qarab BILAN algoritm murakkabligining o'sish tezligi sezilarli darajada farq qilishi mumkin.
5-misol:
Vaqt murakkabligi formula bilan yozilsin
T (N) = 3n2 –100n + 6 = O (n2)
3n2> 3n2 –100n + 6, n³ 1, C = 3.
Agar C1» 0 (C1 = 0,00001), keyin tengsizlik
10-5 n2 > 3 n2 –100 n+6, n³ 1
bajarilmagan.
Ammo murakkablikning o'sish tartibini ko'rsatish mumkin
3n2 –100n + 6¹ O (N).
C * N< 3N2, N>C.
3n2 –100n + 6 = (n2)
C=2.29, n ³ n0.
2.99* n2 < 3 n2 –100 n+6