Вычислительная сложность с «фиксированной размерности»

Question

После того, как я прочитал в научной статье:

Вычислительная сложность алгоритма O(N^d), где N является количество данных, d размерность. Следовательно, при фиксированном размере сложность алгоритма является полиномиальной.

Теперь это заставило меня подумать, что (если я не ошибаюсь), обозначение big-O определяется числом двоичных входов. Таким образом, если я фиксирую размерность данных, естественно прийти к полиномиальному решению. Более того, если бы я также исправить N, количество входных данных, я бы прийти к O(1) решения см подключенную пост: Algorithm complexity with input is fix-sized

Мой вопрос, если вы думаете, что это правильный аргумент для полиномиальной сложности? Можно ли действительно исправить одно измерение и входные данные и потребовать многочленную сложность?

Answer 1

Да, это разумная вещь.

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

Вы можете сравнить решение со сложностью O (d^N), где исправление количества измерений не означает, что решение является полиномиальным. Таким образом, представленный явно лучше, когда d мало.

Answer 2

В качестве быстрого отзыва из университета. Обозначение Big-O - это всего лишь UPPER как работает ваш алгоритм. Математически, F (X) = О (г (х)) означает, что существует константа к> 0 и х0, что

F (X) < = кг (х) для всех х> х0

Чтобы ответить на ваш вопрос, вы не можете исправить N, которая является независимой переменной. Если вы исправите N, сообщите < 100, мы можем с уверенностью прийти к O (1), , потому что в соответствии с определением. Мы можем установить большой K для обеспечения f (N) < = kG (N) для всех x (< 100)

Answer 3

Это работает только для некоторых алгоритмов. Мне непонятно, что такое «измерение» должно быть в некоторых случаях.

E.g. SubSetSum является NP-полным, поэтому нет алгоритма, известного с полиномиальной сложностью. Но ввод - это всего лишь N чисел. Вы также можете увидеть это как N номеров бит d. но алгоритм все еще имеет многочленную сложность.

То же самое относится к самой короткой векторной задаче (SVP) для решеток. Вход представляет собой базовый элемент N x N (скажем, с целыми записями), и вы ищете кратчайший ненулевой вектор. Это также тяжелая проблема, и алгоритм с полиномиальной сложностью пока не известен.

Answer 4

Для многих проблем не только размер входных данных, что затрудняет задачу, но и определенные свойства или параметры этих данных. Например. многие проблемы графа имеют сложность, заданную в числе узлов и ребер отдельно.

Иногда разница между этими параметрами может быть драматичной, например, если у вас есть что-то вроде O (n^d), сложность является просто полиномиальной, когда n растет, но экспоненциально, когда d растет.

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

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

Так что исправление всех параметров обычно не является вариантом, потому что должен быть один аспект, в котором размер ваших данных меняется. Это может быть вариант, если ваша сложность очень медленно растет.

E.g. структуры данных с операциями O (log n) иногда считаются эффективными с постоянной сложностью, если константа также довольно мала. Или структуры данных как объединения-находки-структуры, где амортизированная сложность операций равна O (α (n)), где α - обратная функция Аккермана, функция растет настолько медленно, что невозможно получить выше 10 или для любого размер n любое аппаратное воображение могло бы когда-либо справиться.