(1/2)^n的Big O类别是什么？

Question

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

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

然而，当涉及到渐近分析和Big O时，我们倾向于使用很多手势和引用公式。1/2在技术上是一个常数，因此似乎会落入O(c^n)中。

我倾向于O(c^n)，因为谈到算法时，“半个操作”毫无意义。哪个算法随着输入的增大只需要一半的时间？最好情况下，我认为数学公式(1/2)^n指的是某个时间常数的一半——比如一分钟。因此，(30秒)^n成为一个巨大的数字，函数显然属于O(c^n)。

需要帮忙吗？

- zzu

---

递减函数在运行时/空间成本分析中并没有太大用处，但在数值误差分析中却经常出现。在这种情况下，1和1/n以及1/2^n之间的差异非常重要。当然，由于大O符号类似于<=，因此1/n显然是O(1)。也许你想问的是大Theta符号吧？ - Craig Gidney

我正在尝试将一系列数学函数按照增长顺序从最小到最高进行排序。上述函数是其中之一。而我正试图弄清楚它应该属于O(logn)这样的级别还是O(n^3)这样的级别以上。 - zzu

那么确定，大O符号是有效的... (1/2)^n 属于哪个大O符号类别？ - zzu

并不一定有一个固定的“大O类别”集合，所有函数都可以归入其中，许多函数最好用它们自己来描述。您能详细说明您的问题吗？这是从哪里来的？这是一个问题集问题吗？ - templatetypedef

我在想是否有一种连贯的方式可以用渐近分析来讨论这种类型的函数。如果没有，那没关系。在算法中你不能真正谈论负n（负大小的数据集毫无意义），所以也许这是同样的情况。考虑到数学和计算机科学之间的共同点，我想知道是否有人已经建立了一个关于如何处理这种类型函数的规则。 - zzu

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ⁿ) 是最强和最准确的陈述。

- Ami Tavory

---

谢谢，@Am_I_Helpful！ - Ami Tavory

Answer 2

你不能写出一个O(1/2^N)的算法，因为当N趋近于无穷大时，运行时间会变得非常小，这在物理上是不可能的。你不能少于一次“操作”。

- Malcolm McLean

---

大 O 表示法并不仅仅描述时间行为。 - user824425

我不同意。Big-O 的主要用途之一是描述“时间复杂度”。在计算机科学中比较算法时，我认为这并不罕见？ - zzu

@Malcolm McLean 我倾向于同意你的观点。也许在算法的背景下这没有任何意义。但是，我想检查一下是否已经就这种类型的函数达成了某种共识。我知道我在其他地方看到过它，但我从未明确地处理过它。 - zzu