algorithm - 指数时间复杂度示例 (n^n)

Question

我一直无法找到真正的计算需要 n^n 次计算的算法示例(编程或现实世界)。我看过旅行商问题，但那真的是 n!略小于 n^n。我还看过电话簿示例 here .这个电话簿问题并不是真正的 n^n，因为每个原始电话簿加载总共需要 n 并且为每个原始电话簿制作 n 个副本。现在是 n + n^2。然后机器人需要加载每个额外的副本，这也是 n^2。把所有这些加起来，你得到 n + 2n^2。因为我们看的是最大的指数，所以只有 x^2。

谁能给我一个真正需要 n^n 的例子吗？

Answer 1

递归 O(nⁿ) 函数的一个例子，计数为 nⁿ

long long pownn(int n, int depth) {
    if ( ! depth) return 1;
    long long ll = 0;
    int i = n;
    while (i--) ll += pownn(n, depth-1);
    return ll;
}

调用了long long result = pownn(n, n);

这种算法就像在某些游戏中可以找到的那样，理论上每个可搜索位置都会给自己 n 个其他可搜索位置，搜索深度设置为 n。实际上，可以优化游戏(如国际象棋)(minimax/alpha-beta/memoization-like:数百万位置存储/位置分析......)，并且搜索可能比深度n更远消除“无用”的中间位置。因此，“仅”分析了数百万个职位。