«Информатиканың теориялық негіздері»


-ДӘРІС. Алгоритмдердің тиімділігі мен күрделілігіне анализ жасау



бет42/80
Дата07.01.2022
өлшемі0,6 Mb.
#20727
1   ...   38   39   40   41   42   43   44   45   ...   80
Байланысты:
«Информатиканы теориялы негіздері»

10-ДӘРІС. Алгоритмдердің тиімділігі мен күрделілігіне анализ жасау.

Қарастырылатын сұрақтар: Алгоритмнің күрделілігі ұғымы. Алгоритмнің асимптотикалық күрделілігі. Есептің күрделілігі. Күрделіліктің жоғарғы, төменгі және орташа бағасы. Алгоритмнің асимптотикалық уақытша күрделілігі. Әр түрлі алгоритмдердің тиімділігін салыстыру.

Алгоритмдер анализіне кіріспе

Алгоритмдердің салыстырмалы бағалары


Практикалық есептерді шешуге арналған алгоритмдерді қолдану кезінде біз есепті шешу алгоритмін орынды таңдау мәселесімен кездесеміз. Таңдау мәселесін шешу салыстырмалы бағалар жүйесін құрумен байланысты. Ол өз кезегінде алгоритмнің формальды моделіне сүйенеді.

Ары қарай жалпы мәселеге қолданылатын Пост анықтамасына сүйене отырып, дұрыс және финитті алгоритмдерді, яғни жалпы мәселенің 1-шешімін беретін алгоритмдерді қарастырамыз. Формальды жүйе ретінде адрестік жадыны және жоғарғы деңгей тіліне сәйкестендірілген «элементар» амалдар жиынтығын қолдайтын фонНеймандық архитектуралы процессорды қамтитын абстрактілі машинаны қарастырамыз.

Ары қарай талдау мақсатында келесі ережелерді орнатамыз:


  • әр команда бекітілген уақыттан артық орныдалмайды;

  • алгоритмнің бастапқы берілгендері әрбіреуі биттен болатын машиналық сөздермен беріледі.

  • Нақты мәселе жадының N сөзімен беріледі, осылайша,алгоритм кірісінде = N* бит ақпарат. Кей жағдайларда әсіресе матрицалық есептерді қарастырғанда N алгоритм кірісінің сызықтық өлшемін бейнелейтін ұзындық өлшемі болып табылатынын атап өтейік.

Жалпы мәселені шешу алгоритмін жүзеге асыратын программа әрбіреуі биттер – = М* бит ақпарат болатын М машиналық инструкциядан тұрады.

Сонымен қатар, алгоритм абстрактілі машинаның келесі қосымша ресурстарын талап ете алады:



  • – аралық нәтижелерді сақтауға арналған жады;

  • – есептеу процесін ұйымдастыруға арналған жады (рекурсиялық шақырулар мен қайтаруларды жүзеге асыруға қажетті жады).

Жадының N сөзімен берілген нақты мәселені шешу кезінде тек финитті алгоритмдерді қарастыру шартында алгоритм абстрактілі машинаның «элементар» амалдарының шекті санынан артығын орындамайды. Осыған байланысты келесі анықтаманы енгізейік:

Анықтама 4.1. Алгоритмнің еңбеккөлемділігі.

Берілген нақты кіріс - (N) үшін алгоритмнің еңбеккөлемділігі деп осы формальды жүйедегі нақты мәселені шешу үшін алгоритм орындайтын «қарапайым» амаладар санын ұғамыз.



Алгоритмнің комплексті анализі нақты есептер шешу үшін алгоритм талап ететін формальды жүйенің ресурстарын комплекстті бағалау негізінде орындала алады. Әрине, әртүрлі қолданылу облыстары үшін ресурстар салмақтары әртүрлі болды, бұл келесі алгоритмдерді комплексті бағалауға алып келеді:

, мұндағы – ресурс салмақтары.


  1. Достарыңызбен бөлісу:
1   ...   38   39   40   41   42   43   44   45   ...   80




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет