§5.2 Полиномиальные и экспоненциальные алгоритмы

Теория сложности алгоритмов определяет общие типы алгоритмов, дифференцируя их по

трудоемкости на два класса:

полиномиальные алгоритмы;

экспоненциальные алгоритмы.

Алгоритм, обе функции сложности которого полиномиальные, называется

полиномиальным алгоритмом.

Алгоритм, у которого хотя бы одна из двух функций сложности экспоненциальная,

называется экспоненциальным алгоритмом.

Задача, решаемая полиномиальным алгоритмом, называется легкоразрешимой

задачей.

Задача, которую нельзя решить полиномиальным алгоритмом,

трудноразрешимой.

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

Неразрешимость есть крайний случай экспоненциальности.

Пример:

f(x)=2x+3, p1(x)=3x+7, p2(x)=1+x5, g(x)=x3.

2x+3 ≤ (3x+7)∙x3 и x3 ≤ (1+x5)∙(2x+3)

=> f(x) и g(x) полиномиально связаны или эквивалентны.

Вопрос 50

Полиномиальные и экспоненциальные алгоритмы

Временная сложность алгоритма — это, в худшем случае, функция размера входных данных, которая показывает максимальное количество элементарных операций, затрачиваемые алгоритмом для решения экземпляра задачи указанного размера.

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

Пространственная сложность алгоритма — это, в худшем случае, функция размера входных данных, которая показывает максимальное количество памяти, затрачиваемое алгоритмом для решения экземпляра задачи указанного размера.

В наилучшем случае - функция размера входных данных, которая показывает минимальное количество памяти, затрачиваемое алгоритмом для решения экземпляра задачи указанного размера.

Теория сложности алгоритмов определяет общие типы алгоритмов, дифференцируя их по трудоемкости на два класса:

полиномиальные алгоритмы;

экспоненциальные алгоритмы.

Алгоритм, обе функции сложности которого полиномиальные, называется полиномиальным алгоритмом.

Алгоритм, у которого хотя бы одна из двух функций сложности экспоненциальная, называется экспоненциальным алгоритмом.

Задача, решаемая полиномиальным алгоритмом, называется легкоразрешимой задачей.

Задача, которую нельзя решить полиномиальным алгоритмом, называется трудноразрешимой.

В число трудноразрешимых задач входят алгоритмически неразрешимые задачи. Неразрешимость есть крайний случай экспоненциальности.