Теория алгоритмов

Цель анализа — нахождение оптимального алгоритма. Критерий — трудоёмкость (количество необходимых алгоритму элементарных операций). Функция трудоёмкости — соотношение трудоёмкости с входными данными.

На трудоёмкость могут в разной мере влиять свойства входных данных:

• Объём;
• Значения;
• Порядок поступления.

Один из упрощённых видов анализа затратности алгоритмов — асимптотический, с большим объёмом входных данных. Используемая оценка функции трудоёмкости — «сложность» алгоритма, позволяющая определить связь трудоёмкости с объёмом данных. В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Ниже перечислены основные оценки сложности.

Основной оценкой функции сложности алгоритма ${\displaystyle f(n)}$ (где n — величина объёма данных, «длина входа») является ${\displaystyle {\boldsymbol {\Theta }}}$:

${\displaystyle f(n)={\boldsymbol {\Theta }}(g(n))}$

если при g > 0 при n > 0 существуют положительные с₁, с₂, n₀, такие, что:

${\displaystyle c_{1}\cdot g(n)\leq \;f(n)\leq \;c_{2}\cdot g(n)}$

при ${\displaystyle n>n_{0}}$; иначе говоря, можно найти такие ${\displaystyle c_{1}}$ и ${\displaystyle c_{2}}$, что, — при достаточно больших ${\displaystyle n}$, — ${\displaystyle f(n)}$ будет заключена между:

${\displaystyle c_{1}\cdot \;g(n)}$ и ${\displaystyle c_{2}\cdot \;g(n)}$.

В таком случае говорят ещё, что функция ${\displaystyle g(n)}$ является асимптотически точной оценкой функции ${\displaystyle f(n)}$, так как по определению функция ${\displaystyle f(n)}$ не отличается от функции ${\displaystyle g(n)}$ с точностью до постоянного множителя (см. асимптотическое равенство). Например, для метода сортировки «heapsort», оценка трудоёмкости составляет:

${\displaystyle f(n)={\boldsymbol {\Theta }}(n\log n)}$, то есть ${\displaystyle g(n)=n\log n}$.

Из ${\displaystyle f(n)={\boldsymbol {\Theta }}(g(n))}$ следует ${\displaystyle g(n)={\boldsymbol {\Theta }}(f(n))}$.

${\displaystyle {\boldsymbol {\Theta }}(g(n))}$ представляет собой не функцию, а множество функций, описывающих рост ${\displaystyle f(n)}$ с точностью до постоянного множителя. ${\displaystyle {\boldsymbol {\Theta }}}$ даёт одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка ${\displaystyle {\boldsymbol {O}}}$ представляет собой верхнюю асимптотическую оценку трудоёмкости алгоритма. Мы говорим, что ${\displaystyle f(n)={\boldsymbol {O}}(g(n))}$, если:

${\displaystyle \exists \;c>0,n_{0}>0:0\leq \;f(n)\leq \;cg(n),\forall \;n>n_{0}}$.

Иначе говоря, запись ${\displaystyle f(n)={\boldsymbol {O}}(g(n))}$ означает, что ${\displaystyle f(n)}$ принадлежит классу функций, которые растут не быстрее, чем функция ${\displaystyle g(n)}$ с точностью до постоянного множителя.

Оценка ${\displaystyle {\boldsymbol {\Omega }}}$ задает нижнюю асимптотическую оценку роста функции ${\displaystyle f(n)}$ и определяет класс функций, которые растут не медленнее, чем ${\displaystyle g(n)}$ с точностью до постоянного множителя. ${\displaystyle f(n)={\boldsymbol {\Omega }}(g(n))}$, если:

${\displaystyle \exists \;c>0,n_{0}>0:0\leq \;c\,g(n)\leq \;f(n),\forall \;n>n_{0}}$.

Например, запись ${\displaystyle f(n)={\boldsymbol {\Omega }}(n\,\log n)}$ обозначает класс функций, которые растут не медленнее, чем ${\displaystyle g(n)=n\,\log n}$; в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

Равенство ${\displaystyle f(n)={\boldsymbol {\Theta }}(g(n))}$ выполняется тогда и только тогда, когда ${\displaystyle f(n)={\boldsymbol {O}}(g(n))}$ и ${\displaystyle f(n)={\boldsymbol {\Omega }}(g(n))}$.

Асимптотический анализ алгоритмов имеет не только практическое, но и теоретическое значение. Так, например, доказано, что все алгоритмы сортировки, основанные на попарном сравнении элементов, отсортируют n элементов за время, не меньшее ${\displaystyle {\boldsymbol {\Omega }}(n\,\log n)}$.

Важную роль в развитии асимптотического анализа алгоритмов сыграли Aльфред Ахо, Джеффри Ульман, Джон Хопкрофт.

В рамках классической теории, осуществляется классификация задач по их сложности (P-сложные, NP-сложные, экспоненциально сложные и другие):

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

Класс «P» содержится в «NP». Классическим примером NP-задачи является «Задача о коммивояжёре».

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

Исследования сложности алгоритмов позволили по-новому взглянуть на решение многих классических математических задач и найти для некоторого их ряда (умножение многочленов и матриц, решение линейных систем уравнений и другие) решения, требующие меньше ресурсов, нежели традиционные.