algorithm - (1/2)^n 的大 O 类

函数 (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)。一点帮助？ 最佳答案 函数 0.5n 是 O(1)，对于任何 c > 0 也是 O(c)(它不是 O(0)，因为对于任何 n 0.5n > 0)。它也是 o(1) (注意 little o )。对于任何常数 c，它都不是 Θ(c)。如果 c = 0，问题是对于任何 n，0.5n > c。对于任何 c > 0，lim n → ∞ 0.5n 就我个人而言，我认为说它是 Θ(0.5n) 是这里最强和最准确的说法。关于algorithm - (1/2)^n 的大 O 类，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39821973/