Amaliy oqibatlar Eng yomon holatda ishlashi yomon bo'lgan ko'plab algoritmlar yaxshi o'rtacha ish ko'rsatkichlariga ega. Biz hal qilmoqchi bo'lgan muammolar uchun bu yaxshi narsa: bizni qiziqtirgan holatlar o'rtacha ekanligiga umid qilishimiz mumkin. Kriptografiya uchun bu juda yomon: biz kriptografik muammoning odatiy holatlari qiyin bo'lishini xohlaymiz. Bu erda tasodifiy o'z-o'zini kamaytirish kabi usullar eng yomon holat o'rtacha holatdan qiyin emasligini yoki ekvivalent tarzda o'rtacha holat eng yomon holatdan oson emasligini ko'rsatish uchun ba'zi bir aniq muammolar uchun ishlatilishi mumkin.
Boshqa tomondan, xesh-jadvallar kabi ba'zi ma'lumotlar tuzilmalari eng yomon holatlarning xatti-harakatlariga ega, ammo etarli hajmdagi yaxshi yozilgan xesh jadvali statistik jihatdan hech qachon eng yomon holatni bermaydi; bajarilgan operatsiyalarning o'rtacha soni eksponensial yemirilish egri chizig'iga to'g'ri keladi va shuning uchun operatsiyaning ishlash vaqti statistik jihatdan cheklangan.
Oddiy so'zlar bilan aytganda, kirish hajmi n bo'lgan muammo uchun:
Eng yaxshi holat = optimal kiritishlar tanlangan holda bajarish uchun eng tez vaqt. Misol uchun, saralash algoritmi uchun eng yaxshi holat allaqachon tartiblangan ma'lumotlar bo'ladi.
Eng yomon holat = pessimal kiritishlar bilan yakunlashning eng sekin vaqti. ...
O'rtacha holat = o'rtacha arifmetik.
Oldingi postda biz Asimptotik tahlil algoritmlarni tahlil qilishning sodda usuli muammolarini qanday yengishini muhokama qilgan edik. Ushbu postda biz Lineer Search misolini olamiz va uni Asimptotik tahlil yordamida tahlil qilamiz.
Algoritmni tahlil qilish uchun uchta holatga ega bo'lishimiz mumkin:
1) Eng yomon holat
2) O'rtacha holat
3) Eng yaxshi holat
1-misol:
Keling, chiziqli qidiruvning quyidagi amalga oshirilishini ko'rib chiqaylik.
Eng yomon holatlar tahlili (odatda bajariladi)
Eng yomon tahlilda biz algoritmning ishlash vaqtining yuqori chegarasini hisoblaymiz. Biz maksimal miqdordagi operatsiyalarni bajarishga olib keladigan ishni bilishimiz kerak. Chiziqli qidiruv uchun eng yomon holat izlanadigan element (yuqoridagi kodda x) massivda mavjud bo'lmaganda sodir bo'ladi. Agar x mavjud bo'lmasa, search() funksiyasi uni arr[] ning barcha elementlari bilan birma-bir solishtiradi. Shuning uchun chiziqli qidiruvning eng yomon vaqt murakkabligi D (n) bo'ladi.
O'rtacha holatlar tahlili (ba'zan bajariladi)
O'rtacha vaziyatni tahlil qilishda biz barcha mumkin bo'lgan ma'lumotlarni olamiz va barcha kirishlar uchun hisoblash vaqtini hisoblaymiz. Barcha hisoblangan qiymatlarni jamlang va yig'indini kirishlarning umumiy soniga bo'ling. Biz ishlarning taqsimlanishini bilishimiz (yoki bashorat qilishimiz) kerak. Chiziqli qidirish muammosi uchun barcha holatlar bir xil taqsimlangan deb faraz qilaylik (jumladan, massivda x mavjud bo'lmagan holat). Shunday qilib, biz barcha holatlarni yig'amiz va yig'indini (n+1) ga bo'lamiz. Quyida o'rtacha vaqt murakkabligi qiymati keltirilgan.
Eng yaxshi vaziyat tahlili (soxta)
Eng yaxshi vaziyatni tahlil qilishda biz algoritmning ishlash vaqtining pastki chegarasini hisoblaymiz. Biz minimal miqdordagi operatsiyalarni bajarishga olib keladigan ishni bilishimiz kerak. Chiziqli qidirish muammosida eng yaxshi holat x birinchi joyda mavjud bo'lganda yuzaga keladi. Eng yaxshi holatda operatsiyalar soni doimiy (n ga bog'liq emas). Shunday qilib, eng yaxshi holatda vaqt murakkabligi T (1) bo'ladi.
Ko'pincha biz algoritmlarni tahlil qilish uchun eng yomon holatlar tahlilini qilamiz. Eng yomon tahlilda biz algoritmning ishlash vaqtining yuqori chegarasini kafolatlaymiz, bu yaxshi ma'lumotdir.
Ko'pgina amaliy holatlarda o'rtacha vaziyatni tahlil qilish oson emas va u kamdan-kam hollarda amalga oshiriladi. O'rtacha vaziyatni tahlil qilishda biz barcha mumkin bo'lgan ma'lumotlarning matematik taqsimotini bilishimiz (yoki bashorat qilishimiz) kerak.
Eng yaxshi holat tahlili soxta. Algoritmning pastki chegarasini kafolatlash hech qanday ma'lumot bermaydi, chunki eng yomon holatda algoritm bir necha yillar davom etishi mumkin.
Ba'zi algoritmlar uchun barcha holatlar asimptotik jihatdan bir xil, ya'ni eng yomon va eng yaxshi holatlar mavjud emas. Masalan, Birlashtirish tartibi. Merge Sort barcha holatlarda D(nlogn) amallarini bajaradi. Boshqa saralash algoritmlarining aksariyati eng yomon va eng yaxshi holatlarga ega. Misol uchun, tez tartiblashning odatiy amalga oshirilishida (burchak elementi sifatida pivot tanlangan), eng yomoni kirish massivi allaqachon tartiblangan bo'lsa va eng yaxshisi pivot elementlari massivni har doim ikki yarmiga bo'lganda sodir bo'ladi. Kiritilgan saralash uchun eng yomon holat massiv teskari tartiblanganda va eng yaxshi holat massiv chiqish bilan bir xil tartibda tartiblanganda sodir bo'ladi.
2-misol:
Ushbu misolda biz (n) uzunlikdagi massivni olamiz va quyidagi holatlarni ko'rib chiqamiz:
Agar (n) juft bo'lsa, bizning chiqishimiz 0 bo'ladi
Agar (n) toq bo'lsa, bizning chiqishimiz massiv elementlarining yig'indisi bo'ladi.
Quyida berilgan muammoning kodi:
Xulosa Algoritmni tanlashda bir nechta muhim fikrlar mavjud.
1.Trening ma'lumotlarining hajmi. Ishonchli bashoratlarni olish uchun odatda yaxshi miqdordagi ma'lumotlarni to'plash tavsiya etiladi. ...
2. Chiqishning aniqligi va/yoki talqin qilinishi. ...
3. Tezlik yoki mashg'ulot vaqti. ...
4. Chiziqlilik. ...
5. Xususiyatlar soniga etibor berishimiz kerak!
