Алгоритм анализа для задачи ранца против алгоритма сортировки

Question

Я изучаю анализ алгоритмов и методы проектирования в алгоритмах. При изучении проблемы ранца упоминается, что хотя ранцем является O (nW), где n - количество предметов, а W - вес. Это не полином, как объяснено ниже.

Размер входных данных - это log (W) бит для веса (и O (n) для массивов "value" и "weight").

Итак, входной размер веса равен j = log (W) (а не просто W). Итак, W = 2ʲ (используется двоичный код).

Конечная сложность O (n * W)

Этот O (n * W) можно переписать как O (n * 2). ^ j), экспоненциальный по размеру входных данных.

С приведенным выше аргументом все алгоритмы, например, алгоритм сортировки, имеют значение O (nlogn), которое также становится экспоненциальным, так как «n» выражается как 2 ^ j.

Я запутался.

Answer 1

Определение того, работает ли алгоритм за «полиномиальное время», требует более строгого определения «входного размера», чем требуется для описания времени работы алгоритма. Например, следующий алгоритм выполняется за время O (n), но не за полиномиальное время:

count_down(n)
    i = n
    while i > 0 do
        i--

l oop повторяется n раз и выполняет O (1) * за одну итерацию, где n является входным числом, поэтому его временная сложность составляет O (n). В большинстве ситуаций нет проблем с утверждением, что этот алгоритм занимает время O (n).

Однако, в целях определения того, работает ли алгоритм за полиномиальное время, мы имеем в виду, является ли его время выполнения ограничен полиномиальной функцией входного размера , обычно измеряемой в битах. Число битов, необходимых для представления числа n, равно log₂ n, так что это размер ввода, и O (n) не ограничен полиномом в log₂ n.

Это не относится к алгоритмам сортировки , поскольку для тех n означает длину массива, а не величину числа. Невозможно представить массив длины n, используя только O (log n) битов; это занимает O (n) бит. Таким образом, время выполнения O (n log n) или O (n²) ограничено полиномиальной функцией размера ввода в этом случае, потому что размер ввода равен n вместо log is n. Это подразумевает, что такие алгоритмы сортировки выполняются за полиномиальное время.

_{* Предостережение: уменьшение целого числа требует O (1) амортизированного времени, если целое число изменено на месте. На языке, подобном Python, где целые числа являются неизменяемыми объектами, это занимает O (log n) времени из-за необходимости копировать столько битов в новый объект.}