(1/2)^n 的大 O 级

Question

函数 (1/2)^n 属于哪个 Big O 类？

从纯粹的数学角度来看，我们似乎必须将其放入 O(1) 中，因为对于任何足够大的 n，1/2^n 都接近 0。

然而，当涉及到渐近分析和大O时，我们往往会做很多手把手的工作，并且还会回顾公式。1/2 从技术上讲是一个常数，因此看起来会落入 O(c^n) 的范围。

我倾向于 O(c^n) 因为在谈论算法时说“半个操作”是没有意义的。当输入变大时，什么算法需要一半的时间？充其量，我看到数学公式 (1/2)^n 指的是某个时间常数的一半 - 比如说一分钟。所以 (30 秒)^n 变成了一个巨大的数字，并且该函数显然属于 O(c^n) 。

一点帮助？

Answer 1

函数0.5 ⁿ是O(1)，对于任何c > 0也是O(c)（它不是O (0)，因为对于任何n 0.5 ⁿ > 0）。

它也是o(1)（注意小 o）。

对于任何常数c来说，它都不是θ(c)。如果c =0，问题是对于任何n ，0.5 ⁿ > c。对于任何c > 0，lim _{n → ∞} 0.5 ⁿ < c。

就我个人而言，我认为说θ(0.5 ⁿ )是这里最有力、最准确的说法。