Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. Asimptotik analiz. Algoritmlarni analiz qilish

Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. Asimptotik analiz. Algoritmlarni analiz qilish

O'tgan postda biz asimptotik analiz nima ekanligi bilan tanshgan edik, Ushbu postda biz chiziqli qididiruv algoritmini asimptotik analiz qilamiz.
Algoritmni analiz qilishda 3 xil holat bo'lishi mumkin:
1) Eng yomon holat
2) O'rtacha holat
3) Eng zo'r holat
Quyida chiziqli qidiruv algoritimining realizatsiyasi keltirilgan:
#include
int search(int arr[], int n, int x)
{
int i;
for (i=0; i{
if (arr[i] == x)
return i;
}
return -1;
}
int main()
{
int arr[] = {1, 10, 30, 15};
int x = 30;
int n = sizeof(arr)/sizeof(arr[0]);
printf("%d soni %d inchi indexda topildi", x, search(arr, n, x));
getchar();
return 0;
}
Eng yomon holat
Eng yomon holatda biz algoritmni eng ko'p vaqt oladigan holatini qaraymiz. Bu holat — eng baland chegara (Upper bound) deb ham ataladi. Chiziqli qidiruv algoritmida eng yomon holat — qidirilayotgan x son arr massivda mavjud bo'lmasligi. Chunki, agar arr massivda qidirilayotgan element mavjud bo'lmasa, search() funksiyasi massivni barcha elementlarini bilan bitta-bitta qarab chiqadi. Ushbu turdagi analiz eng keng foydalaniladi.
O'rtacha holat
O'rtacha holatda algoritmni ishlash vaqtini topish uchun, barcha sonlarni topish uchun ketgan vaqtlarni (har bir sonni alohida-alohida topishga ketgan vaqtlar) o'rta arifmetigi olinadi. Odatda amaliyotda, bu analiz juda ham ko'p ishlatilmaydi, chunki bu holtda biz programma qabul qilishi mumkin bo'lgan barcha qiymatlarni bilishimiz kerak bo'ladi.
Eng zo'r holat
Eng zo'r holat bu algoritmni bajarilishi uchun ketgan eng kam vaqtli holatdir. Chiziqli qidiruv algoritimida, agar qidirilayotgan son massivda birinchi bo'lib turgan bo'lsa sodir bo'ladi. Bu turdagi analiz amaliyotda deyarli umuman ishlatilmaydi, chunki eng zo'r holat faqat shartli sonlardagina bajarilishi mumkin.
Esda tuting: Algoritmlarni asimptotik analiz qilishda odatda eng yomon holat analizidan foydalaniladi. Ya'ni algoritmning ishlash vaqti uning eng yomon holati bilan baholanadi.
Asimptotik baholash turlari O - eng yomon holat

F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchamini n> 0 ko'rib chiqing .

Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , n ₀ > 0 , keyin

0<="" i="">

uchun n> n ₀ .
Bu holda g (n) funktsiya f (n) ning asemptomatik ravishda aniq qiymatidir. Agar f (n) algoritmning murakkabligi funktsiyasi bo'lsa, unda murakkablik tartibi f (n) - O (g (n)) deb belgilanadi.
Bu ibora g (n) dan doimiy omilgacha tez o'smaydigan funktsiyalar sinfini belgilaydi.
Asimptotik funktsiyalarga misollar

f (n)	g (n)
2n ^2 + 7n - 3	n 2
98n * ln (n)	n * ln (n)
5n + 2	n
8	1

Ω - eng yaxshi ball

Ta'rif eng yomon holatlar uchun smeta ta'rifiga o'xshaydi, ammo

f (n) = Ω (g (n)), agar

0<="" i="">

Ω (g (n)) o'sadigan funktsiyalar sinfini aniqlasa. g (n) funktsiyadan doimiy omilgacha sekinroq bo'lmaydi .

Θ - o'rtacha ish uchun ball

Ta'kidlash joizki, n> n ₀ uchun f (n) funktsiya hamma joyda c ₁ * g (n) va c ₂ * g (n) orasida bo'ladi , bu erda c doimiy omil. Masalan, f (n) = n ² + n bilan ; g (n) = n ² .
Algoritmni baholash mezonlari
Og'irlikni o'lchashning yagona mezoni (RVC) algoritmning har bir bosqichi vaqtning birligida va xotira xujayrasi bitta hajm birligida (doimiyga aniq) bajarilishini taxmin qiladi.

Logarifmik o'lchov mezoni (LCV) ma'lum bir operatsiya bilan ishlov berilgan operand hajmini va xotira hujayrasida saqlanadigan qiymatni hisobga oladi.

LCV vaqt murakkabligi l (O _p ) qiymati bilan belgilanadi , bu erda O _p - operandning qiymati.

LCV ning sig'im murakkabligi l (M) qiymati bilan belgilanadi , bu erda M - xotira xujayrasining kattaligi.

Eng yomon ish samaradorligini tahlil qilish va o'rtacha ish samaradorligini tahlil qilish ba'zi o'xshashliklarga ega, ammo amalda odatda turli xil vositalar va yondashuvlar talab etiladi.