O(N^N) 是什么复杂度类？

Question

我正在研究 N-Queens 问题的一个天真的解决方案 [0]，该解决方案的最坏情况下的性能为 O(N^N)，我很好奇是否有该复杂性类的名称，或者它是否只是归为“阶乘” “？

[0] http://www.cs.ucc.ie/~dgb/courses/toc/handout25.pdf

Answer 1

很抱歉让您失望，但该类称为 DTIME(n ⁿ )（从技术上讲，您需要一个决策问题，例如，给定 k 和 n，是否至少有 k 个不同的 n-Queens 解决方案？）。它没有一个花哨的名字，因为它对复杂性理论家来说并不那么有趣。它包含在EXPTIME 中，它是所有多项式 p(n)的 DTIME(2 ^p(n) ) 的并集。朴素的 n-Queens 算法实际上见证了子类PSPACE 的成员资格，因为它仅使用 O(n) lg(n) 位存储字，即多项式位数。人们普遍假设 PSPACE 是 EXPTIME 的严格子类。