Рубрики

Псевдополиномиальные алгоритмы

Что такое псевдополином?
Алгоритм, сложность которого в наихудшем случае зависит от числового значения ввода (а не количества входов), называется псевдополиномиальным алгоритмом.
Например, рассмотрим проблему подсчета частот всех элементов в массиве положительных чисел. Псевдополиномиальное временное решение для этого состоит в том, чтобы сначала найти максимальное значение, затем выполнить итерацию от 1 до максимального значения, и для каждого значения найти его частоту в массиве. Это решение требует времени в соответствии с максимальным значением во входном массиве, поэтому псевдополином. С другой стороны, алгоритм, временная сложность которого основана только на количестве элементов в массиве (не на значении), считается алгоритмом полиномиального времени.

Псевдополином и NP-полнота
Некоторые NP-полные задачи имеют решения с псевдополиномиальным временем. Например, решения динамического программирования для задач 0-1: рюкзак , сумма подмножеств и разбиений являются псевдополиномиальными. NP-полные задачи, которые можно решить с помощью алгоритмов псевдополиномиального времени, называются слабо NP-полными.

Ссылка:
https://en.wikipedia.org/wiki/Pseudo-polynomial_time

Рекомендуемые посты:

Псевдополиномиальные алгоритмы

0.00 (0%) 0 votes