2-modul. Algoritmlar samaradorligini baholash mezonlari

Algoritm murakkabligi va samaradorligi tushunchalari.

Algoritmlarni tahlil qilishning bir qator muhim sabablari mavjud. Ulardan biri algoritmning muvaffaqiyatli ishlashi uchun zarur bo‘ladigan kompyuter xotirasi hajmining yuqori chegarasi yoki talab qilinadigan vaqt bahosi hisoblanadi.
Algoritm sifatini baholashda algoritmning murakkabligi yoki unga teskari bo‘lgan – algoritm samaradorligi tushunchalari kiritiladi. Algoritm qanchalik ko‘p vaqt va qanchalik katta hajmli xotira talab qilsa, uning samaradorligi shunchalik past bo‘ladi.
Algoritm murakkabligi quyidagi qismlardan tashkil topadi:

• 
  vaqt bo‘yicha murakkablik;
  
• 
  xotira hajmi bo‘yicha murakkablik.
  

Vaqt bo‘yicha murakkablik – bu algoritm ishlashi uchun talab qilinadigan vaqt mezonidir. Xotira hajmi bo‘yicha murakkablik esa – algoritmning kompyuter xotirasiga bo‘lgan talabini tavsiflaydi. Ushbu mezonlarning aniq shakliga qarab algoritm murakkabligi amaliy va nazariy murakkablikka bo‘linadi.
Amaliy vaqt bo‘yicha murakkablik odatda vaqt o‘lchov birliklari (sekundlar, millisekundlar, protsessorning vaqtli taktlari soni, sikllarning bajarilish soni va h.k.) da baholanadi. Xotira hajmi bo‘yicha amaliy murakkablik bitlarda, baytlarda, so‘zlarda va

11. 
    ifodalanadi. Nazariy murakkablik tushunchasiga keyinroq batafsil to‘xtalamiz. Algoritmning murakkabligiga ta’sir qiluvchi asosiy faktorlarni sanab o‘tamiz:
    
    • 
      kompyuterning ishlash tezligi va uning xotira resurslari, birinchi navbatda tezkor (operativ) xotirasining hajmi. Haqiqatan ham, protsessorning chastota takti va tezkor xotira hajmi qancha kichik bo‘lsa, arifmetik va mantiqiy amallarning bajarilishi shuncha sekinlashadi, shuningdek, tashqi xotiraga murojaat (katta o‘lchamli masalalar uchun) ham ko‘payadi. Buning oqibatida algoritmni ishlatish uchun ko‘p vaqt yo‘qotiladi.
      
    • 
      Tanlab olingan dasturlash tili. Masalan, assembler tilida tuzilgan dastur, boshqa yuqori darajali tillarda tuzilgan dasturga nisbatan tez ishlaydi.
      
    • 
      masala uchun qurilgan matematik model.
      
    • 
      dasturchining tajribasi va dasturlash san’ati. Boshlovchi dasturchiga qaraganda tajribali dasturchi ancha samarali dastur tuzishi mumkin.
      

Algoritmlarning samaradorligini taqqoslashning yaxshi usuli – bu uning murakkablik darajasini solishtirish hisoblanadi. Bu usul ham vaqt bo‘yicha, ham xotira hajmi bo‘yicha murakkablikka tadbiq qilinadi. Algoritmning murakkablik darajasi undagi qayta ishlanadigan berilganlarning soniga qarab aniqlanadi. Masalan, ma’lum bir algoritm undagi qayta ishlanadigan massiv o‘lchoviga bog‘liq bo‘lsin. Agar massiv tartibi ikki marta kattalashganda, algoritm bajarilishiga ketadigan vaqt ham ikki marta oshsa, u holda vaqt bo‘yicha murakkablik ham massiv o‘lchovi kabi bo‘ladi. Algoritmning tartibi – bu matematik funksiya bo‘lib, vaqt murakkabligi aniq ifodasini beradi.
Ma’lum bir masalani yechadigan turli algoritmlar mavjud. Bu algoritmlar ichidan eng samaralisini tanlab olish turli omillarga asosan amalga oshiriladi [1]. Algoritm samaradorligini aniqlashdan oldin, uning qo‘yilgan masalani to‘g‘ri yecha olishini isbotlash kerak bo‘ladi, aks holda uning samaradorligini baholashning hojati qolmaydi.
Algoritmni tahlil qilishdan maqsad – algoritm uchun ma’lumotlarni muvaffaqiyatli qayta ishlash jarayonida kerak bo‘ladigan kompyuter xotirasi hajmi va ishlash vaqtining baholari hamda chegaralarini olish hisoblanadi. Algoritmda bajariladigan arifmetik, mantiqiy va h.k. amallar soni, uning qo‘yilgan masalani kompьyuterda echishga sarflanadigan vaqtini ifodalaydi. “Vaqt” birligi algoritm samaradorligini baholashda unchalik muhim emas [2].
Aslida bizni algoritm samaradorligini baholashda, qaralayotgan algoritmdagi amallar soni emas, balki algoritmga kiritiladigan berilganlar hajmi, ya’ni n oshib borishi bilan undagi amallar sonining qanday tezlikda oshishi muhim
hisoblanadi.

Demak, biz bir masalani yechadigan ikki va undan ortiq algoritmlarni taqqoslash uchun qandaydir sonli mezon topishimiz kerak bo‘ladi.

2.