Іздестіру, таңдау және сұрыптау алгоритмдеріне талдау жасау

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

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

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

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

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

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