#pragma argsused #include #pragma hdrstop #include

O'sish darajasi (mehnat zichligi) nima?

Algoritmning ishlash vaqtining kirish berilganlarining hajmiga qarab o'sish tezligi o'sish sur'ati deyiladi. Siz mashina va velosiped sotib olish uchun do'konga bordingiz deylik . Agar u yerda bir do'stingiz sizdan nima sotib olasan deb so’rasa, siz mashina sotib olmoqchiman deb javob berasiz. Buning sababi shundaki, mashina narxi velosiped narxidan ancha yuqori .

Yuqoridagi misol uchun biz mashina narxini va velosiped narxini funktsiya nuqtai nazaridan tasavvur qilishimiz mumkin va bu funktsiya uchun siz nisbatan kichik (n ning katta kirish qiymatlari uchun) pastki buyurtma shartlarini e'tiborsiz qoldirasiz .

Masalan, n⁴ , 2n² , 100n va 500 ba'zi funktsiyalarning alohida xarajatlari bo'lsin , shunda etarlicha katta n uchun umumiy xarajatlar n⁴ tartibda bo'ladi , chunki n⁴ o'sish sur'ati bo'yicha eng yuqori ko'rsatkichdir.

f(n) = n⁴ +2n² + 100n +500

Odatda ishlatiladigan o'sish sur'atlari.

Quyidagi diagrammada turli xil o'sish sur'atlari o'rtasidagi bog'liqlik ko'rsatilgan. 

 

Quyida kelgusi ma'ruzalarda ko'rishimiz mumkin bo'lgan o'sish sur'atlari jadvali keltirilgan .

Mehnat hajmi	Nomi	Misol
1	Doimiy	Bog'langan ro'yxatning oxiriga element qo'shish
log n	Logarifmik	Saralangan massivdan elementni izlash
n	Chiziqli	Saralanmagan massivdan elementni izlash
nlogn	Chiziqli  logarifmik	n ta elementni "bo'ling va zabt eting" tamoyili bo'yicha saralash –Sortirovka sliyaniem
n^2	Kvadratik	Grafdagi ikkita tugun orasidagi eng qisqa yo'lni topish
n^3	Kubik	Matritsani matritsaga ko'paytirish
2^n	Eksponentsial	“Xanoy minorasi” masalasi