Алгоритмы полиномиального времени

Question

Однажды я услышал следующую цитату, но забыл, кому она приписывается:

Ожидая остановки алгоритма (полиномиального времени), не забывайте, что ваша жизнь ограниченатоже многочлен.

Может ли кто-нибудь предоставить ссылку?

Другой вопрос, который у меня есть: алгоритмы полиномиального времени хороши, но каков пример алгоритма, используемого на практике?который требует O(n^101), т.е. ограничен полиномом высокой степени?

Answer 1

Скорее всего, любой алгоритм сложности O (n ¹⁰⁰ ) является , а не практичным, что объясняет, почему такие алгоритмы не используются на практике.

Одно повторяющееся семейство высокополиномиальных алгоритмических задач состоит в том, что, когда у вас есть большая коллекция объектов (N объектов), и вам нужно найти «оптимальное» подмножество из k элементов из коллекции в соответствии с заданной произвольной метрикой найти подмножество k элементов с определенным свойством. Единственное всегда применимое решение - перечислить все возможные подмножества. Это немедленно приводит к сложности O (N ^k ) (где k фиксировано). Однако случай с k = 100 трудно представить и не может быть решен на практике для большинства значений N.

Answer 2

Что ж, я не видел O (n ^ 101), но часто непреднамеренно создают алгоритмы высокого порядка, комбинируя другие алгоритмы немного более низкого порядка.По моему опыту, сложность редко ограничивается одной переменной, чаще она выражается в терминах нескольких переменных, например O (A * log (B) log (C) (D ^ 2) * (EF))

В качестве примера, недавно мне было поручено разработать алгоритм для определения местоположения всех потенциальных мест для откачиваемой гидроэлектростанции для данной модели местности с площадью (X) на (Y) метров, составленных из (N) 3d координат.Требовалось найти плоскую область указанной минимальной площади (A) в пределах указанного максимального горизонтального расстояния (H), а минимальная разница высот (Z) другой квартиры имеет указанный минимальный размер.Плоскостность в этом контексте определяется как объем материала, который необходимо переместить, чтобы выровнять область до произвольной отметки (E), ища с вертикальным интервалом (V).Области были определены как многоугольники (S) сторон с диаметром (D), а разрешение поиска было указано в метрах (M).Сложная грубая сила выглядит примерно так:

1) Линейное сканирование для начальной плоской области = O ((X / M) * (Y / M)), эта область будет иметь диапазон высоты Z1до Z2 2) Вычислить плоскостность в текущей позиции, вычислить единичный объем O (S), найти высоту с минимальным объемом O ((((Z2-Z1) / V) * S) 3) Радиально сканировать другую плоскую область, близкую к текущейплоская область O (D / M) и вычисление плоскостности новой области O ((Z3-Z4) / V) * S)

Объединяя это, мы получаем O ((X / M) (Y / M) ((Z2-Z1) / В) S (D / M) (Н / М) ((Z3-Z4) / V),* S) и очевидная потребность в лучшем подходе;)

Сложность возникает в этом случае из-за необходимости поиска в поисках.например, поиск плоских пятен на местности, где само определение плоских пятен требует нетривиального поиска, что, в свою очередь, может привести к большему поиску.Иногда это неизбежно, что приводит к нежелательным уровням сложности.

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