Algoritm korrektligni baholash

Algoritm korrektligni baholash

Algoritmni har qanday shaklda taqdim etgandan so'ng, uning to'g'riligini baholash kerak. Bu shuni anglatadiki, tanlangan algoritm cheklangan vaqt uchun har qanday to'g'ri kirish qiymatlari uchun kerakli natijani beradi. Misol uchun, Euclid algoritmining ikki raqamning tugunlarini hisoblash uchun to'g'riligi, turi GCD (t, n) = GCD (n, m mod n) tengligining to'g'riligidan kelib chiqadi, bu esa o'z navbatida isbotlanishi kerak, shuningdek, har bir iteratsiya bo'yicha ikkinchi raqam har doim kamayadi va ular nolga etib borgach, algoritmni bajarish to'xtatiladi.Ba'zi algoritmlarning to'g'riligini isbotlash juda oson, boshqalari esa juda qiyin. Algoritmning to'g'riligini isbotlashning universal usuli matematik indüksiyon usuli hisoblanadi. Aslida, algoritmlar tabiatan iterativ bo'lib, indüksiyon usuli bilan isbotlashda ishlatiladigan asta-sekin ko'rsatmalar ketma-ketligi sifatida tavsiflanadi. Bu diqqat bilan tanlangan kiritish ma'lumotlar bir necha Odatda, algoritmlar yaratuvchilari bir necha talablarga javob berishga harakat qilishadi. Algoritmning to'g'riligini tekshirgandan so'ng, eng muhim xususiyatlardan biri uning samaradorligini baholashdir. Amalda, algoritmning samaradorligini baholashning ikki turi mavjud: vaqtinchalik va mekansal. Vaqtinchalik samaradorlik (vaqt samaradorligi) algoritmning ishlash tezligi ko'rsatkichidir. Mekansal samaradorlikka (space efficiency) kelsak, bu taxmin algoritmni ishlatish uchun zarur bo'lgan qo'shimcha RAM miqdorini ko'rsatadi.

Agar siz algoritmning samaradorligi, soddaligi yoki umumiyligi bilan qoniqmasangiz, yana qalamni olib, algoritmni qayta ishlashingiz kerak bo'ladi. Va algoritm tahlil ijobiy natijalarga olib keldi bo'lsa ham, u boshqa algoritmik muammoni hal qilish uchun qarash mantiqiy. Avvalgi bobda ko'rib chiqilgan tugunni aniqlash uchun uchta algoritmni esga olish kifoya. Umuman olganda, siz birinchi urinishda muammoning eng yaxshi echimini topishga umid qilishingiz kerak emas. Eng kam narsa, yaratilgan algoritmni optimallashtirishga harakat qilishdir. Har doim mashhur frantsuz yozuvchisi, uchuvchi va samolyot dizaynerlari Antoine De Saint-Exupery (Antoine de Saint-Exupery) ning bayonotini eslang: "dizayner o'zining aql-idrokiga qo'shilmaydigan hech narsa bo'lmasa, mukammallikka erishadi va boshqa hech narsa yo'q bo'lganda".

Algoritmning yana bir muhim xususiyati uning soddaligi (simplicity). Qattiq matematik ifodalar yordamida aniq belgilanishi va baholanishi mumkin bo'lgan samaradorlikdan farqli o'laroq, algoritmning keyingi muhim xususiyatlarining soddaligi uning umumiyligi yoki ko'p qirrali (generality) hisoblanadi. Aslida, bu erda ikkita nuqta bor: muammoni hal qilish uchun algoritm ishlab chiqilgan muammoning umumiyligi va uning kirish ma'l

Bizning algoritmimiz haqiqatan ham to'g'ri ekanligini qanday baholay olamiz? To'g'ri algoritm har qanday kirish uchun to'g'ri chiqish shaklida natija beradigan algoritmdir. Misol uchun, agar biz qidiruv algoritmini ko'rib chiqsak, uning ishining natijasi topilgan elementning indeksi yoki -1 raqami bo'lishi kerak. Algoritmning to'g'riligini tekshirish uchun bir necha usullar mavjud

Matematik indüksiyon usuli Barcha tabiiy sonlar uchun uning haqiqatini isbotlash uchun n bir necha qadamni bajarishi kerak: P eng oddiy holatda - n = 1 uchun haqiqiy ekanligini isbotlang. Bunga indüksiyon bazasi deyiladi. Keyinchalik, bu bayonot ba'zi k uchun to'g'ri ekanligini va k uchun to'g'ri bo'lsa, k + 1 uchun ham to'g'ri ekanligini isbotlaymiz. Bunga indüksiyon bosqichi yoki indüksiyon o'tish deyiladi. Agar biz buni isbotlasak, p ning bayonoti barcha n uchun amal qiladi degan xulosaga kelish mumkin. Faqat matematik misollar o'zingiz uchun qarash mumkin, va men algoritmlar to'g'ridan-to'g'ri harakat qiladi. Misol uchun, ikkilik qidiruv algoritmining to'g'riligini isbotlaylik. Faqat uning kodini beraman:

int binary_search(int arr[], int start, int end, int target)

{

if (start == end)

{

return arr[start] == target ? start : -1;

}
int mid = floor(start + (end - start) / 2);
if (target <= arr[mid])

{

// Левая часть

return binary_search(arr, start, mid, target);

}

else

{

// Правая часть

return binary_search(arr, mid + 1, end, target);

}

}

Ishning to'g'riligini isbotlash uchun biz algoritmning oxirgi qadam soni bo'yicha ishni yakunlashini ko'rsatishimiz kerak. Nima uchun shunday? Algoritm yakunlandi bo'lsa, bu funktsiya, degan ma'noni anglatadi, ikki qismga qator sindirib va to'g'ri massaj bilan o'zini sabab, ertami-kechmi recursion eng past darajada bo'ladi, bir qator bilan muomala qilinadi, bitta element o'z ichiga olgan. Agar shunday bo'lsa, algoritm faqat taqqoslash jarayonini bajarishi va qiymatni qaytarishi mumkin. Taqqoslash operatsiyasining isboti ahamiyatsiz, shuning uchun biz faqat taqdim etilgan har qanday kirish ma'lumotlari bilan algoritm to'g'ri bajarilishi va qiymat qaytarilishi kerakligiga ishonch hosil qilishimiz kerak.

Birinchidan, takroriy qo'ng'iroqlar sonini hisoblaylik. Men buni allaqachon qildim, shuning uchun faqat ⌈log2n⌉deb ayting. Har bir funktsiya chaqiruvi bilan, qator ikki qismga bo'linadi, n ning 2 marta o'sishi faqat bitta qadamni qo'shadi. Mid har doim (bu holda kichik yo'nalishda) yumaloq, chunki, biz, katta yo'nalishda qiymatini yumaloq, va shuning uchun n, qaysi emas, balki bir necha 2, biz bir ikki vaziyatni hosil, qachon, holda, element o'ng tomonida joylashgan bo'lsa, algoritm amalga oshiradi 1 qadam ko'proq. Ta'riflash uchun biz ushbu "eng yomon" holatdan foydalanamiz. Natijada, dalil, eng past darajadagi recoursiyaning (bir element bilan funktsiya chaqirilganda) to'g'ri bajarilganligini aniqlash kerak, keyin esa eng past darajaga erishish mumkinligini isbotlash kerak.

⌈log2n⌉=0. Agar bir element bir qator bilan vazifasini chaqirganda, qo'ng'iroq zanjiri to'xtaydi, algoritm operator return qoqiladi, deb, qaysi topilgan element o'rnini qaytaradi, yoki -1. Keyinchalik, bizning bayonotimiz k = n uchun to'g'ri deb hisoblaymiz. Natijada log log2k+1⌉ tabiiy son bo'ladi - k tabiiy sondir va har qanday tabiiy sonning logaritmasi salbiy son bo'lishi mumkin emas. Olingan javob katta tomonga yumaladi, bu esa uni tabiiy songa aylantiradi.