Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi Reja



Yüklə 0,53 Mb.
səhifə2/13
tarix02.12.2023
ölçüsü0,53 Mb.
#137210
1   2   3   4   5   6   7   8   9   ...   13
4.2-ma\'ruza

Asimptotik Tahlil
O'tgan darsda biz asimptotik Tahlil nima ekanligi bilan tanshgan edik, Ushbu postda biz chiziqli qididiruv algoritmini asimptotik Tahlil qilamiz.
Algoritmni Tahlil 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 Tahlil 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 Tahlil 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 Tahlil amaliyotda deyarli umuman ishlatilmaydi, chunki eng zo'r holat faqat shartli sonlardagina bajarilishi mumkin.
Esda tuting: Algoritmlarni asimptotik Tahlil qilishda odatda eng yomon holat Tahlilidan foydalaniladi. Ya'ni algoritmning ishlash vaqti uning eng yomon holati bilan baholanadi.

Yüklə 0,53 Mb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8   9   ...   13




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin