Почему задача о рюкзаке псевдополиномиальна?

Время выполнения составляет O (NW) для задачи о неограниченном рюкзаке с N элементами и рюкзаком размера W. W не является полиномиальным по длине входных данных, что делает его псевдо -полиномиальным.

Рассмотрим W = 1 000 000 000 000. Для представления этого числа требуется всего 40 бит, поэтому размер ввода = 40, но вычислительная среда выполнения использует множитель 1 000 000 000 000, который равен O (2 ⁴⁰).

Таким образом, время выполнения более точно называется O (N 2 ^{бит в W}), что является экспоненциальным.

Также см:

• Как понять, что проблема с рюкзаком является NP-полной?
• NP-полнота рюкзака
• Сложность алгоритма динамического программирования для задачи о рюкзаке 0-1 / а>
• Псевдополиномиальное время

В большинстве наших проблем мы имеем дело с большими списками чисел, которые удобно помещаются в стандартные типы данных int / float. Из-за того, что большинство процессоров построено так, чтобы обрабатывать 4-8 байтовых чисел за раз без дополнительных затрат (по сравнению с числами, которые умещаются, скажем, в 1 байт), мы редко сталкиваемся с изменением времени работы из-за увеличения наших чисел или в пределах диапазонов, с которыми мы сталкиваемся в реальных проблемах, поэтому доминирующим фактором остается просто количество точек данных, n или m факторов, к которым мы привыкли.

(Вы можете представить, что нотация Big-O скрывает постоянный множитель, который делит 32 или 64 бита на данные, оставляя только количество точек данных, когда каждое из наших чисел соответствует этому количеству бит или меньше )

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

Уловка с алгоритмом ранца, который мы обсуждали, заключается в том, что он необычно чувствителен (по сравнению с другими алгоритмами) к величине определенного параметра W. Добавьте один бит к W, и вы удвоите время работы алгоритма. Мы не видели такого драматического отклика на изменение значения в других алгоритмах до этого, поэтому может показаться, что мы относимся к Knapsack по-другому, но это настоящий анализ того, как он реагирует неполиномиальным образом. к изменениям размера ввода.

Насколько я понимаю, емкость была бы O (W), если бы входная емкость была массивом [1,2, ..., W], который имеет размер W .Но вход емкости - это не массив чисел, а одно целое число. Временная сложность связана с отношением к размеру ввода. размер целого числа - это НЕ значение целого числа, а количество представляющих его битов. Позже мы преобразуем это целое число W в массив [1,2, ..., W] в алгоритме, заставляя людей ошибочно думать, что W - это размер, но этот массив не является входным, а само целое число.

Думайте о вводе как о «массиве материалов», а о размере - как о «количестве материалов в массиве». Входной элемент фактически представляет собой массив из n элементов в массиве, поэтому size = n. Ввод емкости НЕ является массивом чисел W в нем, а единственным целым числом, представленным массивом логических (W) битов. Увеличьте его размер на 1 (добавив 1 значащий бит), W удваивается, поэтому время выполнения удваивается, отсюда экспоненциальная временная сложность.

Время выполнения алгоритма ранца зависит не только от размера ввода (n - количество элементов), но и от величины ввода (W - вместимость ранца) O (nW), которая экспоненциально зависит от того, насколько оно представлен в компьютере в двоичном формате (2 ^ n). Вычислительная сложность (т.е. то, как обработка выполняется внутри компьютера с помощью битов) связана только с размером входных данных, а не их величинами / значения.

На мгновение не обращайте внимания на список значений / веса. Допустим, у нас есть экземпляр с вместимостью рюкзака 2. W будет принимать два бита во входных данных. Теперь увеличим вместимость ранца до 4, оставив оставшуюся часть входа. Наши вводимые данные выросли всего на один бит, но вычислительная сложность увеличилась вдвое. Если мы увеличим емкость до 1024, у нас будет всего 10 битов ввода для W вместо 2, но сложность увеличится в 512 раз. Сложность времени растет экспоненциально с размером W в двоичном (или десятичном) представлении. .

Еще один простой пример, который помог мне понять концепцию псевдополинома, - это наивный алгоритм проверки простоты. Для заданного числа n мы проверяем, делится ли оно поровну на каждое целое число в диапазоне 2..√n, поэтому алгоритм занимает √ (n − 1) шагов. Но здесь n - это величина входных данных, а не размер.

                     Now The regular O(n) case

Напротив, поиск в массиве данного элемента выполняется за полиномиальное время: O (n). Это занимает не более n шагов, и здесь n - размер входных данных (длина массива).

[ глянь сюда ]

Расчетные биты, необходимые для хранения десятичного числа

Сложность зависит от ввода. В задаче о рюкзаке входами являются размер, максимальная вместимость и прибыль, массивы веса. Мы создаем таблицу dp как size * W, поэтому мы чувствуем ее полиномиальную временную сложность. Но вход W является целым числом, не массивом. Таким образом, это будет O (размер * (количество битов, необходимых для хранения данного W)). Если ни один из битов не увеличивается на 1, время работы удваивается. Таким образом, он экспоненциальный, а значит, псевдополиномиальный.