Почему проблема рюкзака является псевдополиномиальной?
Я знаю это Knapsack является NP-полным, в то время как это может быть решено DP. Они говорят, что решение DP pseudo-polynomial, поскольку оно экспоненциально по "длине ввода" (то есть количеству битов, необходимых для кодирования ввода). К сожалению, я не получил это. Кто-нибудь может объяснить это pseudo-polynomial что для меня медленно?
5 ответов
Время выполнения равно O(NW) для неограниченной задачи о ранце с N предметами и ранцем размера W. Хотя W не является полиномиальной по длине входного значения, что делает его псевдополиномиальным.
Рассмотрим W = 1 000 000 000 000. Для представления этого числа требуется всего 40 бит, поэтому входной размер = 40, но время выполнения вычислений использует коэффициент 1 000 000 000 000, который равен O (240).
Таким образом, время выполнения более точно называется O(N.2бит в W), что является экспоненциальным.
Также см:
В большинстве наших проблем мы имеем дело с большими списками чисел, которые удобно помещаются в стандартные типы данных int/float. Из-за того, что большинство процессоров построены так, чтобы обрабатывать 4-8-байтовые числа за один раз без дополнительных затрат (по сравнению с числами, которые вмещаются, скажем, в 1 байт), мы редко сталкиваемся с изменением времени выполнения от увеличения наших чисел или в пределах диапазонов, с которыми мы сталкиваемся в реальных проблемах - таким образом, доминирующим фактором остается только огромное количество точек данных, n или m факторов, к которым мы привыкли.
(Вы можете себе представить, что нотация Big-O скрывает постоянный коэффициент, который делит 32 или 64 бита на элемент данных, оставляя только количество точек данных, когда каждое из наших чисел укладывается в такое количество бит или меньше)
Но попробуйте переработать другие алгоритмы, чтобы воздействовать на наборы данных, включающие большие целые числа - числа, для представления которых требуется более 8 байтов, - и посмотрите, что это влияет на время выполнения. Величина используемых чисел всегда имеет значение, даже в других алгоритмах, таких как двоичная сортировка, когда вы выходите за пределы буфера безопасности, обычные процессоры дают нам "бесплатно", обрабатывая пакеты по 4–8 байт.
Уловка с алгоритмом рюкзака, который мы обсуждали, заключается в том, что он необычно чувствителен (по сравнению с другими алгоритмами) к величине определенного параметра, W. Добавьте один бит к W, и вы удвоите время работы алгоритма. Мы не видели такого драматического отклика на изменения стоимости в других алгоритмах до этого, поэтому может показаться, что мы относимся к ранцу иначе - но это подлинный анализ того, как он реагирует неполиномиальным образом изменения в размере ввода.
Как я понимаю, это то, что мощность была бы 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 как размер * W, поэтому мы чувствуем ее полиномиальную временную сложность. Но вход W является целым числом , а не массивом . Таким образом, это будет O(размер *(количество битов, необходимых для хранения данного W)). Если ни один из битов не увеличивается на 1, время работы удваивается. Таким образом, он экспоненциальный, а значит, псевдополиномиальный.