Algoritmlar samaradorligini tahlil qilish

Murakkablik algoritmi uchun
Agar kirish hajmi ikki baravar oshsa, u holda ish vaqti
1	bir xil bo'lib qoladi
logn	doimiy ravishda ortadi
N	ikki barobar ortadi
n2	to'rt barobar
n3	sakkiz barobar ortadi
2n	o'quvchi uchun mashq sifatida qoldiriladi

1. Tahlil asoslari

Tezroq ishlaydigan kompyuterning ta'siri
Tezroq ishlaydigan kompyuter belgilangan vaqt ichida katta muammolar to'plamini hal qilishi mumkin, ammo eksponensial vaqt algoritmlari uchun yaxshilanish juda kichik.

For an algorithm of complexity	If you can solve a problem of this size on your 100MHz PC	Then on a 500MHz PC you can solve a problem set of this size	And on a supercomputer one thousand times faster than your PC you can solve a problem set of this size
N	100	500	100000
n2	100	223	3162
n3	100	170	1000
2n	100	102	109

1. Tahlil asoslari

polinom va eksponensial vaqt
Ko'rib turganingizdek, polinom va eksponensial vaqt o'rtasidagi farq juda katta. Biz kompyuterlarda yuqori tartibli polinomli vaqt algoritmlarining juda katta muammolarini juda tez hal qila olamiz, ammo eksponensial vaqt algoritmlari uchun biz minglab dunyodagi eng tezkor superkompyuterlarni birlashtira olamiz va hali ham bir nechta o'lchamdagi o'nlab muammolar to'plamini hal qila olmaymiz. Shunday qilib, muammolarni tavsiflash uchun quyidagi atamalar ishlatilgan:

Polynomial-time Algorithms	Exponential-time Algorithms
Good	Bad
Easy	Hard
Tractable	Intractable