Algoritmlarning samaradorligi va ularning tahlili



Download 1,05 Mb.
bet1/5
Sana30.12.2021
Hajmi1,05 Mb.
#90106
  1   2   3   4   5
Bog'liq
Algoritmlarning effektivligi va ularning tahlili


Algoritmlarning samaradorligi va ularning tahlili.

Bitta masalaning o’zi, samaradorligi jihatidan farq qiluvchi har hil usul va unga mos algoritm yordamida echilishi mumkin. Agar ma’lumotlar tuzilmasi elementlari soni kam bo’lsa, ularni qayta ishlovchi algoritmlar orasida farq samaradorlir nuqtai nazaridan bo’lmasligi mumkin, lekin elementlar soni oshgan sari bunday farq ko’rinadi. Algoritmlar samaradorligini solishtirish uchun ularni samaradorlik darajasini(chegarasini) o’lchash J. Hartmanis va Richard E. Sterns tomonidan ishlab chiqilgan.

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=cn1 chiziqli bog’liqlik bo’lsa, u holda ma’lumotlarni bir necha marta, hususan 5 marta oshirish natijasida, ularni qayta ishlashga ketgan vaqt ham 5 marta oshadi ya’ni n2=5n1 bo’lsa , t2=5t1 o’rinli bo’ladi. Shunga o’xshash, agar bog’liqlik t1=log2n bo’lsa, u holda n 2 marta oshirilsa vaqt sarfi bor yo’g’i bir birlikka ortadi, ya’ni t2=log22n=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 funksiya 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 deyiladiva u samaradorlikni aniqlovchi funksiya ma’lum xadlarni hisobga olganda yoki samaradorlikni aniq hisoblas qiyin, yoki mumkin bo’lmaganda qo’llaniladi.

Quyidagi misolni ko’ramiz:



(1)

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.



1-rasm. Hadlarning funksiya qiymatiga ta’sir qilish miqyosi.



2. 0- katta notasiya.

Algoritm samaradorligini baxolovchi funksiyaning o’sish sur’atini baxolash uchun 0- katta belgilash 1894 yil P. Bachmann tomonidan keltirilgan. Berilgan ikkita f va g funksiyalar uchun quyidagi ta’rifni keltiramiz:




Download 1,05 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish