«Информатиканың теориялық негіздері»
-ДӘРІС. Алгоритмдердің тиімділігі мен күрделілігіне анализ жасау
жүктеу/скачать 0,6 Mb.
|
- Бұл бет үшін навигация:
- Алгоритмдер анализіне кіріспе
| 10-ДӘРІС. Алгоритмдердің тиімділігі мен күрделілігіне анализ жасау.
Қарастырылатын сұрақтар: Алгоритмнің күрделілігі ұғымы. Алгоритмнің асимптотикалық күрделілігі. Есептің күрделілігі. Күрделіліктің жоғарғы, төменгі және орташа бағасы. Алгоритмнің асимптотикалық уақытша күрделілігі. Әр түрлі алгоритмдердің тиімділігін салыстыру. Алгоритмдер анализіне кіріспеАлгоритмдердің салыстырмалы бағаларыПрактикалық есептерді шешуге арналған алгоритмдерді қолдану кезінде біз есепті шешу алгоритмін орынды таңдау мәселесімен кездесеміз. Таңдау мәселесін шешу салыстырмалы бағалар жүйесін құрумен байланысты. Ол өз кезегінде алгоритмнің формальды моделіне сүйенеді. Ары қарай жалпы мәселеге қолданылатын Пост анықтамасына сүйене отырып, дұрыс және финитті алгоритмдерді, яғни жалпы мәселенің 1-шешімін беретін алгоритмдерді қарастырамыз. Формальды жүйе ретінде адрестік жадыны және жоғарғы деңгей тіліне сәйкестендірілген «элементар» амалдар жиынтығын қолдайтын фонНеймандық архитектуралы процессорды қамтитын абстрактілі машинаны қарастырамыз. Ары қарай талдау мақсатында келесі ережелерді орнатамыз:
әр команда бекітілген уақыттан артық орныдалмайды; алгоритмнің бастапқы берілгендері әрбіреуі биттен болатын машиналық сөздермен беріледі. Нақты мәселе жадының N сөзімен беріледі, осылайша,алгоритм кірісінде = N* бит ақпарат. Кей жағдайларда әсіресе матрицалық есептерді қарастырғанда N алгоритм кірісінің сызықтық өлшемін бейнелейтін ұзындық өлшемі болып табылатынын атап өтейік. Жалпы мәселені шешу алгоритмін жүзеге асыратын программа әрбіреуі биттер – = М* бит ақпарат болатын М машиналық инструкциядан тұрады. Сонымен қатар, алгоритм абстрактілі машинаның келесі қосымша ресурстарын талап ете алады: – аралық нәтижелерді сақтауға арналған жады; – есептеу процесін ұйымдастыруға арналған жады (рекурсиялық шақырулар мен қайтаруларды жүзеге асыруға қажетті жады). Жадының N сөзімен берілген нақты мәселені шешу кезінде тек финитті алгоритмдерді қарастыру шартында алгоритм абстрактілі машинаның «элементар» амалдарының шекті санынан артығын орындамайды. Осыған байланысты келесі анықтаманы енгізейік: Анықтама 4.1. Алгоритмнің еңбеккөлемділігі. Берілген нақты кіріс - (N) үшін алгоритмнің еңбеккөлемділігі деп осы формальды жүйедегі нақты мәселені шешу үшін алгоритм орындайтын «қарапайым» амаладар санын ұғамыз. Алгоритмнің комплексті анализі нақты есептер шешу үшін алгоритм талап ететін формальды жүйенің ресурстарын комплекстті бағалау негізінде орындала алады. Әрине, әртүрлі қолданылу облыстары үшін ресурстар салмақтары әртүрлі болды, бұл келесі алгоритмдерді комплексті бағалауға алып келеді: , мұндағы – ресурс салмақтары. жүктеу/скачать 0,6 Mb. Достарыңызбен бөлісу:
|