Ushbu algoritmda i o’zgaruvchi 0 dan N-1 gacha o’zgarib
kelyapti
hamda uning har bir o’zgarishida j o’zgaruvchi ham shu oraliqda o’zgaryapti.
Demak bunda jami N*N marta takrorlanish sodir bo’lyapti. Bundan esa f(N) =
N*N ga teng bo’ladi va algoritmning murakkabligi O(N*N) ekanligini
aniqlashimiz mumkin.
Endi algoritmni murakkablik darajasini baholashni ko’rib chiqaylik.
Bunda algoritmdagi eng tez o’suvchi qismdan foydalanish kerak bo’ladi.
Tasavvur qiling algoritm N^3 + N murakkablikka ega bo’lsin. Bunda biz
murakkablikni O(N^3) deb olishimiz yetarli bo’ladi. Chunki bu yerda tez
o’suvchi qism bu N^3. Ya’ni +N ta qo’shimcha
amalni hisoblashning hojati
qolmaydi. Misol uchun N=100 bo’lsin, shunda jami 1000100 ta amal bajariladi
va bu N^3 dan atigi 0.01% gagina farq qiladi.
Murakkablikni baholash.
Dasturdagi murakkab algoritmlar asosan funksiya va protseduralarda
bo’ladi. Keling, buni ko’rish uchun Fast hamda Slow
nomli funksiyalar yaratib
olaylik va bu funksiyalarning turli xil ko’rinishdagi murakkabligini baholab
ko’raylik.
Demak ushbu kodni ko’rib chiqamiz.
Slow funksiyasi O(N^3) murakkablikka ega bo’lib unda ichma ich 3 ta for
sikli mavjud: N*N*N. Buni osonlik bilan ko’rish mumkin.
Endi Fast funksiyasini ko’radigan bo’lsak unda ichma-ich 2
ta for sikli
mavjud. Ammo ikkinchi siklda biz Slow funksiyasini chaqirganmiz. Bu esa
algoritmning murakkabligini yanada
oshiradi, ya’ni O(N^2) * O(N^3) = O(N^5).
Both funksiyasida biz ikkala funksiyadan ham foydalandik. Bunda
funksiyalar
ketma-
ket qo’llangani sabab ular ichidan murakkabligi katta
bo’lgan funksiya asosiy funksiyaning murakkabligi bo’ladi ya’ni O(N^2) +
O(N^5) = O(N^5). Endi berilgan N=100 da algoritmning
ishlash vaqtini
ko’radigan bo’lsak u quyidagicha:
Demak bu Both funksiyasi 570 soniyadan ko’proq vaqt ishladi. Boshqa
xarakteristikadagi mashinada bu ko’p yoki kam bo’lishi mumkin.
Xulosa qiladigan bo’lsak oddiy takrorlanish algoritmlarining murakkabligi
undagi takrorlanishlarning soniga bog’liq bo’ladi va buni aniqlash ancha oson.
Dostları ilə paylaş: