Эффективность алгоритма. Временная сложность алгоритма. Полиноминальные и экспоненциальные алгоритм.

http://akak-ich.ru/informatika-effect_alg.php

Алгоритм, в конечном счете, выполняется в машинной системе со специфическим набором команд и периферийными устройствами. Для отдельной системы какой-либо алгоритм может быть разработан для полного исполь­зования преимуществ данного компьютера и поэтому достигает высокой степени эффективности. Критерий, называемый системной эффективностью (sys-tem efficiency), сравнивает скорость выполнения двух или более алгоритмов, которые разработаны для выполнения одной и той же задачи. Выполняя эти алгоритмы на одном компьютере с одними и теми же наборами данных, мы можем определить относительное время, используя внутренние системные часы. Оценка времени становится мерой системной эффективности для каждого из алгоритмов.

При работе с некоторыми алгоритмами могут стать проблемой ограничения памяти. Процесс может потребовать большого временного хранения, ограничивающего размер первоначального набора данных, или вызвать требующую времени дисковую подкачку. Эффективность пространства(space efficiency) — это мера относительного количества внутренней памяти, используемой каким-либо алгоритмом. Она может указать, какого типа компьютер способен выполнять этот алгоритм и полную системную эффективность алгоритма. Вследствие увеличения объема памяти в новых системах, анализ пространственной эффективности становится менее важным.

Третий критерий эффективности рассматривает внутреннюю структуру алгоритма, анализируя его разработку, включая количество тестов сравнения итераций и операторов присваивания, используемых алгоритмом. Эти типы измерений являются независимыми от какой-либо отдельной машинной системы. Критерий измеряет вычислительную сложность алгоритма относительно n, количества элементов данных в коллекции. Мы называем эти критерии вычислительной эффективностью (computational efficiency)алгоритма и разрабатываем нотациюBig-О для построения измерений, являющихся функциями n

В информатике, теория сложности вычислений являетсяразделом теории вычислений, изучающим стоимость работы,требуемой для решения вычислительной проблемы.Стоимость обычно измеряется абстрактными понятиямивремени и пространства, называемыми вычислительнымиресурсами. Время определяется количеством тривиальныхшагов, необходимых для решения проблемы, тогда какпространство определяется объёмом памяти или места наносителе данных. Таким образом, в этой областипредпринимается попытка ответить на центральный вопросразработки алгоритмов: «как изменится время исполнения иобъём занятой памяти в зависимости от размера входа ивыхода?». Здесь под размером входа понимается длинаописания данных задачи в битах (например, в задачекоммивояжера длина входа пропорциональна количествугородов и дорог между ними), а под размером выхода —длина описания решения задачи (оптимального маршрута взадаче коммивояжера).