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

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