algorithm - 证明 n^k = Ω(c^n)

Question

我们如何证明

n^k = Ω(c^n)

我试图按照定义去做

n^k >= 某个常数 * c^n

但我无法为常数获得任何价值。我的意思是我无法正确解决问题

*编辑*

对不起，功能应该是错误的

n^k = O(c^n)

那么我面临的主要障碍是使用定义计算常数的值。

从定义开始：

第 1 步：n^k<= p* (c^n)

第 2 步：(n^k/c^n)<= p

我被困在这里。我试图区分这些功能，因为n-> infinity它的无穷大/无穷大形式，但我仍然无处可去！

证明方程

n^k = O(c^n)

除了尝试获取常量的值之外，我们还可以使用哪些方法？

谢谢。

Answer 1

好吧，如果你区分 k 次的分子和分母，n^k / c^n你会得到你想要的：

k! / (ln c)^k * c^n   ->    0  when n-> Inf

所以不仅

n^k = O(c^n)

但即使

n^k = o(c^n)