(1/2)^n 的大 O class
Big O class for (1/2)^n
函数(1/2)^n会落入哪个大Oclass？
在纯粹的数学基础上，似乎我们必须将其放入 O(1) 中，因为对于任何足够大的 n，1/2^n 接近 0。
然而，当涉及到渐近分析和大 O 时，我们往往会做大量的手工操作，并且还会参考公式。 1/2 在技术上是一个常数，所以看起来会落入 O(c^n).
我倾向于 O(c^n)，因为在谈论算法时说 "half an operation" 毫无意义。当输入变大时，什么算法需要一半的时间？充其量，我看到数学公式 (1/2)^n 指的是某个时间常数的一半——比如一分钟。所以 (30 秒)^n 变成了一个巨大的数字，该函数显然属于 O(c^n).
有点帮助？
您不能编写 O(1/2^N) 算法，因为随着 N 接近无穷大，运行时间将变得无穷小，这在物理上是不可能的。你不能少于一个 "operation"。
函数0.5n是O(1)，也是O(c) 对于任何 c > 0（它是 not O(0)，因为 0.5n > 0 对于任何 n)。
也是o(1)（注little o）。
对于任何常数c，它都不是Θ(c)。如果 c =0，问题是 0.5n > c 对于任何 n.对于任何 c > 0, lim n → ∞ 0.5n < c.
个人认为Θ(0.5n)是最有力最准确的说法
函数(1/2)^n会落入哪个大Oclass？
在纯粹的数学基础上，似乎我们必须将其放入 O(1) 中，因为对于任何足够大的 n，1/2^n 接近 0。
然而，当涉及到渐近分析和大 O 时，我们往往会做大量的手工操作，并且还会参考公式。 1/2 在技术上是一个常数，所以看起来会落入 O(c^n).
我倾向于 O(c^n)，因为在谈论算法时说 "half an operation" 毫无意义。当输入变大时，什么算法需要一半的时间？充其量，我看到数学公式 (1/2)^n 指的是某个时间常数的一半——比如一分钟。所以 (30 秒)^n 变成了一个巨大的数字，该函数显然属于 O(c^n).
有点帮助？
您不能编写 O(1/2^N) 算法，因为随着 N 接近无穷大，运行时间将变得无穷小，这在物理上是不可能的。你不能少于一个 "operation"。
函数0.5n是O(1)，也是O(c) 对于任何 c > 0（它是 not O(0)，因为 0.5n > 0 对于任何 n)。
也是o(1)（注little o）。
对于任何常数c，它都不是Θ(c)。如果 c =0，问题是 0.5n > c 对于任何 n.对于任何 c > 0, lim n → ∞ 0.5n < c.
个人认为Θ(0.5n)是最有力最准确的说法