Algoritmni loyihalash va tahlil qilishga kirish

Algoritmik loyihalarni baholash mezonlari

Algoritmlarning murakkabligini tahlil qilish
Algoritmlarning murakkabligini tahlil qilishdan maqsad bu masalani hal qilishning optimal algoritmini topishdir. Algoritmning optimalligi mezoni sifatida algoritmning murakkabligi tanlanadi, bu algoritm yordamida muammoni hal qilish uchun bajarilishi kerak bo'lgan elementar operatsiyalar soni tushuniladi. Murakkablik funktsiyasi - bu algoritmning kirish ma'lumotlarini elementar operatsiyalar soni bilan bog'laydigan munosabatlar.
Algoritmlarning murakkabligi har xil yo'llar bilan kiritilgan ma'lumotlarga bog'liq. Ba'zi algoritmlar uchun mehnat zichligi faqat ma'lumotlarning miqdoriga, boshqa algoritmlar uchun - ma'lumotlar qiymatlariga bog'liq, ba'zi hollarda ma'lumotlarning kelish tartibi mehnat zichligiga ta'sir qilishi mumkin. Ko'pgina algoritmlarning murakkabligi u yoki bu darajada yuqoridagi barcha omillarga bog'liq bo'lishi mumkin.
Amaliyotda ishlatiladigan soddalashtirilgan tahlil turlaridan biri bu algoritmlarni asimptotik tahlil qilishdir. Asimptotik tahlilning maqsadi bir xil masalani echishga mo'ljallangan turli xil algoritmlar tomonidan sarflangan vaqt va boshqa resurslarni katta miqdordagi kirish ma'lumotlari bilan taqqoslashdir. Algoritmning murakkabligi deb nomlangan asimptotik tahlilda ishlatiladigan mehnat zichligi funktsiyasini baholash, ma'lumotlarning ko'payishi bilan algoritmning mehnat zichligi qanchalik tez o'sishini aniqlashga imkon beradi. Algoritmlarni asimptotik tahlil qilishda matematik asimptotik tahlilda qabul qilingan yozuv ishlatiladi. Asosiy qiyinchiliklar bashoratlari quyida keltirilgan.
Algoritm f (n) ning murakkabligi funktsiyasi uchun asosiy taxmin bu taxmindir. Bu erda n - ma'lumotlar hajmining kattaligi yoki kirish uzunligi. Algoritmning murakkabligini taxmin qilish

agar g> 0 uchun n> 0 uchun ijobiy c1, c2, n0 mavjud bo'lsa, unda:

n> n0 uchun, boshqacha qilib aytganda, c1 va c2 ni topish mumkin, shunda etarlicha katta nf(n) orasida bo'ladi
va .
Bunday holda, ular shuningdek, g(n) funktsiyasi f(n) funktsiyasi uchun asimptotik keskin baho, deyishadi, chunki f(n) funktsiyasi g(n) funktsiyasidan doimiy koeffitsientgacha farq qilmaydi (qarang asimptotik tenglik) ... Masalan, omborlarni saralash usuli uchun mehnat zichligini baholash
ya'ni g (n) = nlogn
dan kelib chiqadi.
funktsiya emas, balki ning doimiy omilgacha o'sishini tavsiflovchi funktsiyalar to'plami ekanligini tushunish muhimdir.

• 
  funktsiya o'sishi uchun yuqori va pastki chegaralarni beradi. Ushbu taxminlarni ko'pincha alohida ko'rib chiqish kerak. bahosi algoritmning murakkabligi uchun yuqori asimptotik taxmindir.
  

5.