Agoritm murakkabligini static va dinamik o’lchovlari. Vaqt va hajm bo’yicha

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