Алгоритмнің асимптотикалық кҥрделілігі

 
91 
қаншалықты  жылдам  шешілетінін  бағалай  аламыз.  Мысалы  біз  N  шамадан 
тҧратын тізімді ӛсу реті бойынша сҧрыптау алгоритмі неше салыстыруды қажет 
ететіндігін  бағалай  аламыз,    немесе  ӛлшемі  NxN  екі  матрицаны  кӛбейту  ҥшін 
неше  арифметикалық  амал  қажет  екендігін  есептей  аламыз.  Мысалы,  тӛрт 
шаманың ҥлкенін табудың екі алгоритмін қарастырамыз: 
 
1. l=a                                     2. іf  a>b then 
                                                     іf a>c then 
    іf   b>l  then                                  іf a>d then      
              l=b                                             return a 
  end іf                                              else                   
  return  a                                              return  d 
 іf c>l then                                        end іf 
         l=c                                             іf c> d then 
 end іf                                                             return c 
  іf d>l then                                             else     
      l=d                                                           return d       
   end іf                                                     end іf 
  return l.                                                    end іf 
           else 
                                                      іf  b>c then 
                                                                іf  b>d then 
                                                                     return    b 
                                                                else 
                                                                        return  d 
                                                                end іf 
                                                          else                                                                     
                                                                         іf c>d then 
                                                                                       return c 
                                                                               else 
                                                                                       return d 
                                                                 end іf 
                                                                          end іf 
                                                                end іf 
 
Бҧл  алгоритмдердің  әрбіреуінде  ҥш  салыстыру  жасалады.  Бірінші 
алгоритмді  оқу  жеңіл  және  тҥсінікті,  бірақ  компьютерде  орындалуда  олардың 
кҥрделілік  деңгейі.  Уақыты  жағынан  алғанда  бҧл  екі  алгоритм  бірдей,  бірақ 
екінші  алгоритм  кӛбірек  жазуы  қажет.  Егер  сандар  немесе  символдар 
салыстырылса,  бҧның  маңызы  ерекше  болмайды,  ал  басқа  типті  деректермен 
жҧмыс  істегенде  оның  маңызы  ӛте  зор  болуы  мҥмкін.  Қазіргі  кездегі 
бағдарламалау  тілінің  кӛпшілігінде  ҥлкен  және  кҥрделі  объектілерді  немесе 
жазбаларды  салыстыру  немесе  операторларын  анықтауға  болады.  Бҧл 
жағдайларда  уақытша  айнымалыларды  қолдану  кӛп  орынды  қажет  етеді. 
Алгоритмдердің  тиімділігіне  анализ  жасағанда  бізді  алдымен  уақыт 

 
92 
қызықтырады,  ал  жады  маңызды  болған  жағдайларда  да  қажет  кезінде 
қарастырамыз. 
   

жүктеу/скачать 1,31 Mb.

Достарыңызбен бөлісу: