Сложность задач

решать машины. Решения этих задач формулируются в виде алгоритмов. Таким

образом, сложность задачи определяется свойствами алгоритмов, решающих ее. Точнее, сложность простейшего алгоритма для решения задачи считается сложностью этой задачи.

f(n) — это некоторая математическая функция от n. То есть

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

списка длиной n так, что исходная задача сортировки разделяется на

две меньших, когда сортируются списки длиной приблизительно n/4. Эти две задачи, в свою очередь, делятся еще раз, и мы получаем четыре задачи сортировки . Этот процесс деления можно представить при помощи дерева на рисунке 1.







Рисунок 1- Дерево деления списка

слиянием при сортировке списка длиной n, получается умножением количества сравнений

на каждом уровне на количество уровней, на которых требуются сравнения. Мы делаем вывод, что оно не превышает n [lg n]. Т.е. алгоритм сортировки слиянием принадлежит О(n lg n). Учитывая тот факт, что сложность задачи сортировки равна Θ(n lg n), можно утверждать, что алгоритм сортировки слиянием является оптимальным решением задачи сортировки в отличии, например, от алгоритма сортировки вставкой, который принадлежит О(n2).

она принадлежит О(f(n)), где f(n) - это полином (многочлен), или

это выражение ограничено полиномом. Набор всех полиномиальных задач обозначается Р.
Поиск задач, принадлежащих Р, является одной из главных проблем вычислительной техники, так как он тесно связан с вопросами о том, существует ли для задач практическое решение. То, что теоретически разрешаемые проблемы, не принадлежащие Р, имеют огромную временную сложность, заставляет признать, что их невозможно решить с практической точки зрения. Ученые, занимающиеся вычислительной техникой, называют такие задачи трудно разрешимыми. В свою очередь, задачи, для которых существуют практические решения, содержатся в Р. Поэтому понимание границ класса Р стало важной областью исследований вычислительной техники.

такие инструкции называются недетерминироваными, а сам алгоритм называют недетерминированным.
Во многих

случаях лишь тонкая грань отделяет детерминированные алгоритмы от недетерминированных. Но различие между ними достаточно очевидно и существенно. Детерминированный алгоритм не надеется на творческие способности механизма, выполняющего алгоритм, тогда как для недетерминированного «алгоритма» они могут быть достаточно важны.

недетерминированного алгоритма, называется недетерминированной полиномиальной задачей (nondeterministic polynomial problem), или

NP-задачей. Класс NP-задач обозначается NP. Обратите внимание, что все задачи из Р также принадлежат NP, так как к любому (детерминированному) алгоритму можно добавить недетерминированную команду, не влияющую на работу алгоритма.

неразрешимыми (для которых нет алгоритмического решения). Более того, в классе

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