我正在查看一些具有多个变量的 Big-O 符号的 True/False 语句，并在下面提出了这个
n^k ∈ O(k^n) - 假
我无法理解这个声明，需要一些说明。
解释是这样的
如果 n 被选择为一个固定值，并且 k → ∞，则等式的左侧变为指数，而右侧为多项式。因此，n^k 不受 k^n 的限制
当 n 被选择为常量且 k → ∞ 时，结论变得清晰，但为什么我们不能反过来，即选择 k 作为常量和 n → ∞?选择 n 作为常量的原因是什么？
最佳答案
的确，根据定义，您必须验证这两种情况。在这个证明中，由于其中一个失败了，所以我们可以说 n^k不在 O(k^n) 中对于任何 k和 n .尽管如果您选择k，另一边是正确的作为常量 ( >1 ) 和 n走向无穷大。
关于algorithm - 多变量的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56511565/