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