Algoritmlar samaradorligini baholash 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	---	---	---

3. 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.
Agar n o’lchov va t vaqt orasida t1=c*n chiziqli bog’liqlik bo’lsa, u holda xajmni bir necha marta, hususan 5 marta, oshirish natijasida, ularni qayta ishlashga ketgan vaqt ham 5 marta oshadi ya’ni n2=5*n bo’lsa, t2=5*t o’rinli bo’ladi. Yoki, agar bog’liqlik t1=logn bo’lsa, u holda n 2 marta oshirilsa vaqt sarfi bor yo’g’i bir birlikka ortadi, ya’ni t2=log2*n=t1+1 bo’ladi. n va t ni bog’liqligini ifodalovchi funksiya odatda murakkab bo’ladi va bunday funksiyani hisoblash katta hajmdagi ma’lumotlarni qayta ishlashda juda muhim hisoblanadi. Hosil qilingan f-ya berilgan funksiyaning tarkibiy samaradorligini bildiradi.Shunga qaramay bu yaqinlashish funksiyaga yaqin hisoblanadi, va katta hajmdagi ma’lumotlar uchun originalga juda yaqin bo’ladi. Samaradorlikning bu o’lchovi assimtotik yaqinlashuvchi o’lchov deyiladi va u samaradorlikni aniqlovchi funksiya ma’lum xadlarini hisobga olganda yoki samaradorlikni aniq hisoblas qiyin, yoki mumkin bo’lmaganda qo’llaniladi.
Agar n o’lchov va t vaqt orasida t1=c*n chiziqli bog’liqlik bo’lsa, u holda xajmni bir necha marta, hususan 5 marta, oshirish natijasida, ularni qayta ishlashga ketgan vaqt ham 5 marta oshadi ya’ni n2=5*n bo’lsa, t2=5*t o’rinli bo’ladi. Yoki, agar bog’liqlik t1=logn bo’lsa, u holda n 2 marta oshirilsa vaqt sarfi bor yo’g’i bir birlikka ortadi, ya’ni t2=log2*n=t1+1 bo’ladi. n va t ni bog’liqligini ifodalovchi funksiya odatda murakkab bo’ladi va bunday funksiyani hisoblash katta hajmdagi ma’lumotlarni qayta ishlashda juda muhim hisoblanadi. Hosil qilingan f-ya berilgan funksiyaning tarkibiy samaradorligini bildiradi.Shunga qaramay bu yaqinlashish funksiyaga yaqin hisoblanadi, va katta hajmdagi ma’lumotlar uchun originalga juda yaqin bo’ladi. Samaradorlikning bu o’lchovi assimtotik yaqinlashuvchi o’lchov deyiladi va u samaradorlikni aniqlovchi funksiya ma’lum xadlarini hisobga olganda yoki samaradorlikni aniq hisoblas qiyin, yoki mumkin bo’lmaganda qo’llaniladi.
Quyidagi misolni ko’ramiz:
n ning kichik qiymatlarida ohirgi had 1000 ning funksiya qiymatini hosil bolishidagi ulushu qolganlariga nisbatan katta hisoblanadi. n=10 bo’lganda 2-xad 100n va ohirgi 1000 xadlar teng bo’ladi va boshqalarga nisbatan funksiya qiymatiga bir xil ta’sir ko’rsatadi. Bu xadlarni funksiya xar bir xadining uning qiymatiga qanday ta’sir qilishining miqyosi n ning har hil qiymatlari uchun quyidagi jadvalda keltirilgan.
Hadlarning funksiya qiymatiga ta’sir qilish miqyosi.
Бахолаш функциялар классификацияси.
Berilgan ikkita f va g funksiyalar uchun quyidagi ta’rifni keltiramiz:
1-ta’rif. f(n) funksiya 0(g(n)) bo’ladi deyiladi, agar shunday musbat c va N sonlar mavjud bo’lsaki , barcha n>=N lar uchun f(n)<=c g(n) tengsizlik bajarilsa.
Bu ta’rifga asosan agar f(n) funksiya 0(g(n)) bo’lsa, u holda uning o’sish tartibi yetarli katta n lar uchun albatta cg(n) funksiya o’sish tartibidan kichik yoki teng bo’lar ekan. Demak, bu holda f(n) funksiya katta n larda cg(n) funksiyadan tez o’sa olmaydi. Bu yerda c va N sonlarini aniqlash muammo bo’lib qoladi, chunki ta’rifda ularni aniqlashning konkret yoli korsatilmagan. Ikkinchidan, bu sonlarga hech qanday shartlar qo’yilmagan. Shuning uchun ularning qiymatlari juda ko’p bo’lishi mumkin
f(n)=2n^2+ 3n+1=O(n^2) (2)
f(n)=2n^2+ 3n+1=O(n^2) (2)
U holda g(n)=n^2 funksiyani tarifdagi funksiya sifatida oluvchi funksiyalardan biri deb xisoblash mumkin. Ta’rifga asosan, c va N lar uchun quyidagi rasmdagi sonlar juftliklarini olish mumkin bo’ladi. (2) funksiya uchun c va N larning qiymatlari.
N va c ning qiymatlarini аniqlash
N va c ning bunday qiymatlarini quyidagi tengsizlikni yechish orqali aniqlanadi:
2n^2+3n+1<=cn^2; (3)
Undan tashqari n ning darajalari bo’yicha ham assimptotik funksiyalarni juda ko’pini olish mumkin. Bu holda eng kichik tartiblisi tanlab olinadi. Bunday noaniqliklarni xal qilish berilgan funksiyadagi kichik tartibli xadlarni barchasini tashlab yuborish va quyidagicha belgilash orqali amalga oshiriladi. Masalan, (1) funksiya uchun
f(n)=n^2+100n+O(log10n)
ko’rinishda olish , (2) funksiya uchun esa f(n)=2n^2+O(n) kabi ko’rinishda olish mumkin bo’ladi.
O- katta funksiyalarning xossalari
Tranzitivlik. Agar f(n) funksiya O(h(n)) bo’lsa, u holda сf(n) funksiya O(h(n)) bo’ladi.
Agar f(n) va g(n) funksiyalarning xar biri O(h(n)) bo’lsa, u holda ularning yig’infisi f(n)+g(n) ham O(h(n)) bo’ladi.
f=an^k funksiya O(n^k) bo’ladi.
f=n^k funksiya ixtiyoriy j>=0 uchun O(n^k+j) bo’ladi.
Agar f(n)=Cg(n) bo’lsa, u holda f(n) funksiya O(g(n)) bo’ladi. Ihtiyoriy a teng emas 1, b teng emas 1 sonlar uchun log(an) funksiya O(log(bn)) bo’ladi.
O- notasiya yordamida funksiyani yuqoridan assimptotik baxolashni ko’rdik. Xuddi shunday baxolashni quyidan ham berish mumkin. Bunday baholashni sigma(Ω) baholash deyiladi va u quyidagicha aniqlanadi:
2- ta’rif. f(n) funksiya Ω(g(n)) deyiladi, agar shunday musbat c va N lar mavjud bo’lsaki , barcha n>=N lar uchun f(n)>=cg(n) tengsizlik o’rinli bo’lsa.
Bu ta’rif ham birinchi ta’rifga juda o’xshash, faqat bu yerda tengsizlik teskaridir.
Yuqoridagi ikkita ta’rifdan foydalanib quyidagio ta’rifni keltirish mumkin.
Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:
Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin: