Algoritmlar samaradorligini tahlil qilish

1. Tahlil asoslari Vaqt murakkabligi

Misol: Ikki kvadrat matritsani ko'paytirish
Example: Multiplying two square matrices
Ichkaridan tashqariga qarab ishlaganda biz k-siklning har bir iteratsiyasida 4 ta massiv indekslash amallari, bitta ko'paytirish, bitta qo'shish va bitta topshiriq borligini ko'ramiz. Yoki, heck, bitta katta summa += a[i][k]*b[k][j] operatsiyasi. j-sikl ichida sumni ishga tushirish va c[i][j] ga tayinlash bilan birga ulardan n tasi mavjud. Bu n+2 ni anglatadimi? Qiyin. Boshqa ikkita operatsiya ko'p ahamiyatga ega emas. Shunga o'xshash dalil bilan biz barcha oddiy for-tsikilni ishga tushirish, sinovdan o'tkazish va oshirish operatsiyalarini e'tiborsiz qoldirishimiz mumkin. Ular tez. Biz qilishimiz kerak bo'lgan narsa - sum += a[i][k]*b[k][j] operatsiyalar sonini sanash - bu haqiqatan ham muhim.
Demak, bizda T(n)=n3 bor.

1. Tahlil asoslari Vaqt murakkabligi

Bu erda tashqi tsikl logn marta, ichki tsikl esa n marta bajariladi, shuning uchun T(n)=nlogn. (Ha, kompyuter fanida logarifmlar uchun standart asos 2 ga teng.)
Misol: Qiziqarli ichki halqa
Example: An Interesting Nested Loop
Yes, the default base for logarithms in Computer Science is 2.

1. Tahlil asoslari Vaqt murakkabligi

Bu erda
Misol: Massivdan oxirgi elementning qiymatini olish
Example: Getting the value of the last element from an array
n=a.lengthn=a.length, and T(n)=1.

1. Tahlil asoslari

Vaqt murakkabligi sinflari
Biz murakkablik funktsiyalarini ularning "o'sish sur'atlari" bo'yicha guruhlashimiz mumkin (bir daqiqada biz buni rasmiylashtiramiz). Misol uchun:

Class sinf	Example misol	Description tavsif