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


Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti



Download 81,03 Kb.
bet2/4
Sana28.06.2022
Hajmi81,03 Kb.
#716041
1   2   3   4
Bog'liq
mustaqil ish 1 asliddin odilov,algoritm

Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti

Bitta masalani hal qilish uchun turli xil algoritmlarni ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, biz hisoblashning qaysi turidan foydalanilganligi to'g'risida kelishib olishimiz kerak .. Algoritmning ishlash vaqti bilan biz bajaradigan elementar qadamlar sonini tushunamiz. Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab qilinadi (masalan, ba'zi murakkab harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x-koordinata bo'yicha saralash"). Qo'ng'iroq qilish (qo'ng'iroq qilish) protsedurasini (ma'lum miqdordagi operatsiyalarni oladi) va uning bajarilishini (bajarilishini) farqlashingiz kerak, ular uzoq davom etishi mumkin.


Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan qiymatdir.

Shunday qilib, biz algoritmning vaqtinchalik T (n) va fazoviy V (n) murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga o'xshash tarzda baholanadi. Baholashning eng oson usuli bu eksperimental usul, ya'ni algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi omillar ta'sir qiladi:

. Dastur algoritmining vaqt murakkabligi;
2. bajariladigan dasturning kompilyatsiya qilingan kodining sifati;
3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari.
Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligini o'lchashning tipik birliklaridan foydalanishga imkon bermaydi (soniya, millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (har bir algoritmni kim dasturlasa) bir xil algoritm uchun har xil baholarni olish mumkin. o'z), turli xil kompilyatorlar va turli xil kompyuterlar.
Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi.
Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud.

Listing 1.3 - ish vaqtini hisoblash bilan qo'shilgan saralash algoritmining soxta kodi


m hissasini qo'shadi (ammo bu ibora ishlatilgan xotira hajmini hisoblash uchun ishlatilmaydi). Barcha qatorlarning hissalarini qo'shsak, olamizInsertion-Sort protsedurasining umumiy bajarilish vaqtini hisoblash uchun har bir satrda uning narxini (operatsiyalar soni) va ushbu satrning necha marta bajarilishini hisobga olamiz. 2 dan n gacha bo'lgan har bir j uchun (bu erda n = uzunlik [A] - massiv o'lchami), 5 qatori necha marta bajarilishini hisoblash kerak, biz bu raqamni tj bilan belgilaymiz. Davr ichidagi chiziqlar cheklovga qaraganda bir marta kamroq bajariladi, chunki oxirgi tekshirish pastadirdan chiqadi. Bir necha marta takrorlangan m satr bajarilgan operatsiyalar umumiy soniga c

Jarayonning ishlash vaqti nafaqat n ga bog'liq, balki kirishning kirish qismida n o'lchamining qaysi qatori bilan ta'minlanganligiga ham bog'liq. Insertion-Sort protsedurasi uchun massiv allaqachon tartiblangan bo'lsa, eng maqbul holat. Keyin 5-chiziqdagi tsikl birinchi tekshiruvdan so'ng tugaydi (chunki A [i] ≤ tugmachasi i = j - 1), shunda hamma tj 1 ga teng, jami vaqt esa

n + b shakli mavjud. Ushbu konstantalar tanlangan qiymatlar bilan belgilanadi c1, ..., c8.Shunday qilib, eng qulay holatda n o'lchovli qatorni saralash uchun zarur bo'lgan vaqt (n), n ning chiziqli funktsiyasi. a va b ba'zi turg'unliklar uchun T (n) = a


Agar qator teskari (pasayish) tartibda joylashgan bo'lsa, ish vaqti


protsedura maksimal bo'ladi: A [j] har bir elementni A [1], ..., A [j - 1] barcha elementlar bilan taqqoslash kerak. Bundan tashqari, tj = j. Chunki

biz eng yomon holatda protsedura vaqti ekanligini tushunamiz


n + s shakliga ega. A, b va c konstantalari bu erda ham c1, ..., c8 qiymatlari bilan aniqlanadi.n2 + bBunday holda, T (n) kvadratik funktsiya, ya'ni. T (n) = a


Odatda algoritmning vaqt murakkabligi n o'lchamidagi ma'lumotlardan T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi.


Nimani aniqlash odatiy kirish vositalar qiyin va ko'pincha bu o'rtacha kirish matematikani tavsiflashni qiyinlashtiradigan xususiyatlarga ega (masalan, ishlashga mo'ljallangan algoritmlarni ko'rib chiqing) torlar matn). Xuddi shunday, ma'lum bir "o'rtacha ish" ni oqilona tavsiflash imkoniyati bo'lgan taqdirda ham (bu algoritmning ba'zi bir qo'llanilishlarida qo'llanilishi mumkin), ular tenglamalarni yanada qiyin tahlil qilishga olib keladi.[2]
Eng yomon holatlar tahlili a beradi xavfsiz tahlil (eng yomon holat hech qachon kamsitilmaydi), ammo haddan tashqari haddan tashqari bo'lishi mumkin pessimistik, chunki bu juda ko'p qadamlarni bajaradigan hech qanday (realistik) ma'lumot bo'lmasligi mumkin.
Ba'zi hollarda xavfsizlikni kafolatlash uchun pessimistik tahlildan foydalanish kerak bo'lishi mumkin. Ammo, ko'pincha, pessimistik tahlil o'ta pessimistik bo'lishi mumkin, shuning uchun haqiqiy qiymatga yaqinlashadigan, ammo optimistik (ehtimol, ma'lum bir muvaffaqiyatsizlik ehtimoli ma'lum bo'lgan) tahlil ancha amaliy yondashuv bo'lishi mumkin. Eng yomon va o'rtacha holatlar tahlili o'rtasidagi farqni bartaraf etish uchun akademik nazariyada zamonaviy yondashuvlardan biri deyiladi yumshoq tahlil.

Algoritm

Ma'lumotlar tarkibi

Vaqtning murakkabligi: eng yaxshi

Vaqtning murakkabligi: O'rtacha

Vaqtning murakkabligi: eng yomoni

Kosmik murakkablik: eng yomoni

Tez saralash

Array

O (n log (n))

O (n log (n))

O (n2)

O (n)

Saralashni birlashtirish

Array

O (n log (n))

O (n log (n))

O (n log (n))

O (n)

Uyma tartib

Array

O (n log (n))

O (n log (n))

O (n log (n))

O (1)

Yumshoq saralash

Array

O (n)

O (n log (n))

O (n log (n))

O (1)

Bubble sort

Array

O (n)

O (n2)

O (n2)

O (1)

Kiritish tartibi

Array

O (n)

O (n2)

O (n2)

O (1)

Tanlov tartibida

Array

O (n2)

O (n2)

O (n2)

O (1)

Bogo sort

Array

O (n)

O (n n!)

O (∞)

O (1)
Ko'pincha bajarish uchun oz vaqt talab qiladigan, lekin vaqti-vaqti bilan ancha katta vaqtni talab qiladigan algoritmlarni tahlil qilishda, amortizatsiya qilingan tahlil (ehtimol cheksiz) seriyasidagi eng yomon ish vaqtini aniqlash uchun ishlatilishi mumkin operatsiyalar. Bu amortizatsiya qilingan eng yomon holat xarajat o'rtacha ish narxiga ancha yaqin bo'lishi mumkin, shu bilan birga ish vaqtining yuqori chegarasini ta'minlaydi.
Eng yomon tahlil tahlil bilan bog'liq eng yomon murakkablik.[3]

Download 81,03 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




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