查找时间复杂度

Finding Time Complexity

对于函数 n^k 和 c^n ，这些函数之间的渐近关系是什么？设k≥1,c≥1为常量

  1. n^k 是 O(c^n)
  2. n^k 是 Ω(c^n)
  3. n^k 是 Θ(c^n)
    4. 以上
  4. None

我的想法：当 c=1 时，对于每个值，n^k > c^n，当 c>1 时，则 C^n > n^k。 所以，建议的答案是 3。n^k 是 Θ(c^n)。

我的想法和答案是否正确？请求您的意见。

这个问题其实有两个答案，取决于c的值：

  • 如果c = 1，则c^n = 1^n = 1。 n^k 对于 k ≥ 1 显然会超过这个，所以答案是 (2).

  • 如果c > 1，则指数c^nfar大于any多项式项，即答案将是 (1).

请注意 (3) 永远不会成立。