Почему время выполнения задачи о ранце в терминах n и 2 числа бит W

Question

Я недавно начал понимать, что означает псевдополином благодаря этой публикации . Тем не менее, мой острый вопрос состоит в том, почему проблема рюкзака при использовании с динамическим программированием имеет время выполнения , а не . Где n - количество элементов, которые рассматриваются для ранца, а - количество битов, необходимых для кодирования W, а - количество возможных состояний (значений) дано х бит. Учитывая, что формальное определение сложности времени определяет размер проблемы как

Размер входных данных для проблемы равен числу битов , необходимых для записи этих входных данных.

Поскольку количество бит для веса не фиксированное, а скорее переменное, самое большее общее количество бит для всех возможныхзначения от 0 до W умножаются на значение n или . С учетом вышесказанного, почему время выполнения для рюкзака в сочетании с динамическим программированием имеет время выполнения , а не . Я знаю, что , но сложность времени относится к размеру ввода как число бит Какие предположения я делаю или какие знания я упускаю, чтобы исправить разрыв.

Answer 1

Вот объяснение, относящееся к размеру входного ранца.

• Количество элементов n может быть представлено O (lg n ) битами;
• n вес предметов: отметив, что вес каждого предмета должен быть ≤ W (в противном случае мы можем игнорировать вес предметов больше, чем W ), мы можем представить вес каждого предмета, используя O (lg )W ) биты для общего количества O ( n lg W ) битов;
• n значения элемента: пусть максимальное значениебыть V . Затем каждое значение элемента может быть представлено с помощью O (lg V ) битов для общего количества O ( n lg V ) битов.

Таким образом, общий размер ввода O (lg n + n (lg W + lg V )) = O( n (lg W + lg V )).

Let b = lg W и v = lg V . Тогда размер ввода O ( n ( b + v )). Теперь обратите внимание, что во время O ( nW ) для решения динамического программирования v явно не отображается, поэтому время выполнения равно O ( nW *)1072 *) = O ( n2 ^ b ).