Tayanch so’zlar

n=
n
n*logn
n^2
n^3
1,5^n
2^n
n!
10
30
18min
10^25y
50
11min
36y
Juda kop
100
12892y
10^17y
----
1000
18min
---
----
----
10000
2min
12kun
--
---
---
100000
3soat
32y
---
---
---
1 mln.
20s
12kun
31710y
---
---
---

---

Asimptotik yuqori chegaralar
Algoritmning samaradorligi bu algoritmni qo’llash uchun qancha kuch talab
qilinishini yoki uning qiymati qanchaligini bildiradi. Bunday qiymat har xil
mezonlar bilan o’lchanishi mumkin. Bu erda ulardan ikkitasini: vaqt va fazo
miqdorinini samaradorlik mezonlari sifatida olinadi. Bunda vaqt mezoni fazodan
muhimroq hisoblanadi, shuning uchun samaradorlik asosan ma’lumotlarnu qayta
ishlashga ketgan vaqtga nisbatan olinadi. Samaradorlikni baholash uchun
mantiqiy birliklar, ya’ni fayl yoki massivning o’lchami n va qayta ishlash uchun
ketgan vaqt miqdori t olinadi

---

Eng yahshi, o’rtacha va eng yomon algoritmlar.
Yuqoridagi misollarga asoslanib shuni aytish mumkinki, algoritmlar samaradorligi
bo’yicha 3 hil bolishi mumrin: 1) Eng yomon holat bunda algoritm masalani echish uchun
maksimal sondagi amallarni bajarishni talab qiladi; 2) Eng yaxshi holat bunda algoritm
masalani echish uchun minimal sondagi amallarni bajarishni talab qiladi; 3) Ortacha holat
bunda algoritm masalani echish uchun maksimal va minimal sonlar orasidagi sondagi
amallarni bajarishni talab qiladi.
Sodda hollarda ortacha samaradorlikni aniqlash algoritmga mumkin bolgan kirishlar, har bir
kirish uchun algoritm asosida bajarilayotgan etaplar sonini aniqlash, 

---

Assimptotik
funksiyani
aniqlash
iterasiyalar
soni
o’zgaruvchan bo’lganda
qiyinlashadi. Bu holat quyidagicha misolda ko’rinishi mumkin.
Assimptotik
funksiyani
aniqlash
iterasiyalar
soni
o’zgaruvchan bo’lganda
qiyinlashadi. Bu holat quyidagicha misolda ko’rinishi mumkin.
Elementlari o’sish tartibida joylashgan eng uzun qism massivning uzunligini
aniqlash kerak bo’lsin. Masalan, [1 8 1 2 5 0 11 12] massivda tartiblangan
elementlardan iborat eng uzun qism massiv [1 2 5] bo’lib, uning uzunligi 3 ga teng.
Eng uzun osuvchi qism massivni aniqlash kodi quyidagicha bo’ladi:
for(i=0,length=1; i
for(i1=i2=k =i;k< n-1 &&a[k]
if(length
length =i2-i1 +1;
}

---