Algoritmlar samaradorligini tahlil qilish

Constant o`zgarmas	λn.1
Fixed number of steps, regardless of input size Kirish hajmidan qat'iy nazar qat'iy qadamlar soni
Logarithmic logarifmik	λn. logn	Number of steps proportional to log of input size kirish hajmi jurnaliga mutanosib qadamlar soni
Polynomial	λn. nk, k≥1	Number of steps a polynomial of input size kirish o'lchamidagi polinomning qadamlar soni
Exponential eksponensial	λn.cn, c>1	Number of steps exponential of input size kirish hajmining eksponentsial qadamlar soni

Bu to'rtta foydali oila, ammo biz yana ko'p holatlarni aniqlashimiz va keltirishimiz mumkin:

1. Tahlil asoslari

Vaqt murakkabligi sinflari
ko'p holatlar:

1. Tahlil asoslari

Vaqt murakkabligi sinflari
Taqqoslash:
Comparison:
Ga - gigayil yoki bir milliard yil.
Ga is a gigayear, or one billion years
Murakkablik sinflarini aniqlash uchun soniyada
bir million mavhum operatsiyani bajaradigan kompyuterni ko'rib chiqaylik
Bu nimani anglatadi. 2n qatorni 0,000001⋅2n qator bilan solishtiring. Ikkinchisi birinchisiga qaraganda bir million marta tezroq ishlaydigan narsani anglatadi, ammo baribir, hatto 50 o'lchamli kirish uchun ham minglab asrlarda ishlash vaqtini talab qiladi.

1. Tahlil asoslari

Fazo murakkabligi
Algoritmning fazo murakkabligi uning hayotiy siklida algoritm talab qiladigan xotira fazosi miqdorini anglatadi. Algoritm tomonidan talab qilinadigan fazo quyidagi ikkita komponentning yigʻindisiga teng:
• Muammo hajmidan mustaqil boʻlgan maʼlum maʼlumotlar va oʻzgaruvchilarni saqlash uchun zarur boʻlgan fazo. Masalan, ishlatiladigan oddiy oʻzgaruvchilar va konstantalar, dastur hajmi va boshqalar.
• Oʻzgaruvchan qism — oʻzgaruvchilar tomonidan talab qilinadigan fazo boʻlib, ularning oʻlchamlari muammoning hajmiga bogʻliq. Masalan, dinamik xotirani ajratish, recursion stack fazo va boshqalar.
Har qanday algoritmning S(P) fazo murakkabligi S(P) = C + SP(I), bu yerda C — tuzalgan (fixed) qism, S(I) esa algoritmning oʻzgaruvchan qismidir, bu I misolning xarakteristikasiga bogʻliq. Hozirgi narsani tushuntirishga harakat qiladigan oddiy misol: