Я смотрел на наивное решение [0] на проблему N-Queens, которая имела наихудшую производительность O (N^N), и мне любопытно, есть ли имя для этого класса сложности или оно просто сосредоточено в "факториал"?Какой класс сложности O (N^N)?
[0] http://www.cs.ucc.ie/~dgb/courses/toc/handout25.pdf
Извините разочаровывать, но класс называется DTIME (n n) (технически вам нужна проблема решения, например, при заданных k и n, существуют ли как минимум k различных решений n-Queens?). У него нет причудливого имени, потому что это просто не так интересно теоретикам сложности. Он содержится в EXPTIME, который является объединением DTIME (2 p (n)) для всех многочленов p (n). Наивный алгоритм n-Queens фактически свидетельствует о членстве в подклассе PSPACE, поскольку он использует только O (n) lg (n) -битные слова хранения, то есть многочленное число бит. Широко распространено мнение, что PSPACE является строгим подклассом EXPTIME.
Интересно ... так как он включен в этот EXPTIME, должен быть многочлен p (n) такой, что 2^p (n) примерно равен n^n, правильно? –
@racarate Не многочлен, а между ними: n lg n, омега (n) и o (n^1.000001). –
Эти классы называются Non Polynomial(NP) время. Поскольку их время работы не имеет вида полинома n, где n - размер входного сигнала.
Некоторые другие пример временной сложности NP может быть время O(2^N), O(N^log(N)) временем алгоритмы Wile полиномиальных может быть O(P(N)) где P(N) многочлен N.
для получения дополнительной информации читайте https://en.wikipedia.org/wiki/NP_(complexity)
Я это знаю, но есть огромная разница в времени выполнения между экспоненциальными и факториальными функциями. Например, алгоритм динамического программирования для TSP переносит его с факториального времени на экспоненциальное время, что очень важно. –
Я вижу, что вы говорите, возможно, я слишком часто использовал термин «класс сложности» - то, что я действительно ищу, - это название улицы. –
Ну, в теории есть классы P и NP, и, очевидно, проблема O (N^N) - это NP –
По формуле Стирлинга n! ~ √2πn (n/e)^n, так что мощность и факториал не так различны. (Принимая логарифмы, вы получаете O (n log (n)) для обоих.) –