Algoritmlar samaradorligini tahlil qilish

1. Tahlil asoslari

Vaqt murakkabligi
Tahlilning hozirgi holati algoritmning nisbiy bajarilishi vaqtining kirishdagi elementlar soniga, ya'ni biz chaqirgan kirishni oqilona kodlash uchun zarur bo'lgan belgilar soniga bog'liq bo'lgan o'lchovni topishdir. Bu esa quyidagicha bo'lishi mumkin:
- Konteynerdagi elementlar soni
- Satr yoki fayl uzunligi
- Polinom darajasi
- Butun sondagi raqamlar (yoki bitlar) soni

1. Tahlil asoslari

Vaqt murakkabligi
Birinchi uchta elementning har biri (elementlar, belgilar, koeffitsientlar/ko'rsatkichlar) chegaralangan o'lchamga ega bo'lgandagina mantiqiy bo'ladi. Misol uchun: agar barcha elementlar 64 bitli butun sonlar bo'lsa, u holda elementlar soni n uchun ishlatilishi mumkin, lekin raqamli qiymatlar cheklanmagan bo'lsa, siz bitlarni hisoblashingiz kerak!
Biz mavhum amallar sonini n ning funksiyasi sifatida hisoblaymiz
Misol: Massivning har bir elementini chop etish

1. Tahlil asoslari Vaqt murakkabligi

Bu erda n=a.length (agar biz massivdagi barcha elementlarning belgilangan o'lchamga ega ekanligini bilsak, bu ko'pincha shunday bo'ladi).

• i ning 1 ishga tushirilishi
• n i ni a.length bilan taqqoslash
• n ning orttirmalari I
• n massivni indekslash operatsiyalari

(a[i] ni hisoblash uchun)

• n System.out.println chaqiruvi

• 1 initialization of i
• n comparisons of i against a.length
• n increments of i
• n array indexing operations (to compute a[i])
• n invocations of System.out.println

Misol: Massivning har bir elementini chop etish
Example: Printing each element of an array
T(n)=n

1. Tahlil asoslari Vaqt murakkabligi

Misol: Massivning har bir elementini chop etish
Example: Printing each element of an array
Barcha operatsiyalar teng yaratilmagan. Chop etish o'sish, solishtirish va indekslash operatsiyalarini to'liq bosib oladi. Shuningdek, n ​​taqqoslash-indeks-chop etish-ko'paytirish operatsiyalariga ega bo'lish haqida gapirishimiz mumkin. Keyin T(n)=n+1. Biz bu bilan shug'ullanayotganimizda, biz ishga tushirish ko'p narsani anglatmasligini tushunib olishimiz mumkin, shuning uchun biz T(n) = n deb yozishimiz mumkin.