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

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.

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