这个递归算法的时间复杂度是大 O 表示法下的什么？

Question

我正在学习算法和数据结构课程。

今天，我的教授说以下算法的复杂度是2ⁿ。

课程结束后，我走到他面前告诉他我认为这是一个O(n)算法，并进行了计算来证明它，想向他展示，但他仍然坚持说不是，并没有给出令人信服的解释。

该算法是递归的，其复杂度如下：

       { 1         if n=1
T(n) = {
       { 2T(n/2)   otherwise

我计算出来它是O(n)，方法如下：

我们扩展一下T(n)：

T(n) = 2 [2 * T(n/(2^2))]
     = 2^2 * T(n/(2^2))
     = 2^2 * [2 * T(n/(2^3))]
     = 2^3 * T(n/(2^3))
     = ...
     = 2^i * T(n/(2^i)).

当T内的项为1时，我们停止计算，即：

n/(2ⁱ) = 1 ==> n = 2ⁱ ==> i = log n

代入后，我们得到：

T(n) = 2^log n * T(1)
     = n * 1
     = O(n).

自从我注意到归并排序算法是O(n log n)的，其复杂度为2T(n/2)+Θ(n)(显然高于2T(n/2))，我一直在想，一个复杂度较低的算法为什么会得到更高的大O值。因为这时候对我来说是违反直觉的。他回答道：“如果你认为这违反了直觉，那么你的数学基础有严重问题。”

我的问题是：

1. 我的论证中是否存在任何谬误？ 2. 最后的情况难道不是违反直觉的吗？

是的，这也是发泄。

- doplumi

---

如果他说它是 O(2^n)，那么他是正确的，因为 O 是一个上限。如果他认为它在 Theta(2^n) 中，那么他是错误的。 - ROMANIA_engineer

尽管我已经根据给定的递归式给出了答案，但如果您编辑帖子并提供正在讨论的算法，仍然会有所帮助。换句话说，“以下算法”是什么？ - John Coleman

@JohnColeman 我刚在你的回答下面评论了这个问题。我把它复制到这里：C教授实际上并没有从算法中得出那个递归关系。一开始，正如我之前所写的，我认为他是要向我们展示归并排序递归关系和这个递归关系之间存在某种反直觉的东西。但当我后来问他时，这一点变得清楚了。现在我真的很困惑他为什么要向我们展示这个。 - doplumi

@helpYou 是的:D 谢谢。我没有考虑到那一点。他说它不是O(n)的，这样说对吗？ - doplumi

它的时间复杂度是O(n)，O(2^n)，O(n^n)，O(nlogn)等等，但不是O(logn)，O(sqrt(n))，O(1)等等。所以，如果他说它不是O(n)，那么他是错的；但如果他说它是O(2^n)，那么他是对的，因为这是真实的，即使这并不太相关。 - ROMANIA_engineer

如果你认为这是违反直觉的，那么你在数学方面有严重的问题。他这样说太不专业了，任何老师都不应该这样说话而不给出任何解释。 - sve

Answer 1

证明 - 1

这个递归落在 Master Theorem 的第三种情况，有：

• a = 2；
• b = 2；
• c = -∞。

因此，Log_ba = 1 大于 -∞。因此，运行时间为 Θ(n¹) = Θ(n)。

---

证明 - 2

直观地说，你将大小为 n 的问题分解成大小为 n/2 的两个子问题，并且连接两个子问题的代价为0（即递归中没有常量部分）。

因此，在最底层，你有n个成本为1的问题，每个问题的运行时间为 O(1)，这导致了运行时间为n * O(1)，即 O(n)。

---

编辑：为了完善这个答案，我还要添加一些你提出的具体问题的答案。

我的论证有什么谬误吗？

没有。是正确的。

最后一种情况不会有违直觉吗？

肯定会有违直觉。请参见上面的证明-2。

- displayName

Answer 2

你说得很对，满足这个递归关系的函数T(n)是O(n)。这显然很明显，因为它表明给定问题的复杂度是其一半大小的问题的两倍。你不能再线性了。例如，使用线性搜索在1000个元素的列表中搜索的复杂度是在500个元素中搜索的两倍。

如果您的教授也是正确的，那么您可能对满足该递归的复杂度不正确。或者，有时会对如何测量输入大小存在一些困惑。例如，一个整数n在指定它所需的位数方面是指数级的。例如，整数n的暴力试除法是O(sqrt(n))，比O(n)好得多。之所以这不与暴力分解在破解RSA方面基本无用相矛盾，是因为对于256位密钥，相关的n约为2^256。

- John Coleman

---

C教授并非从算法中得出该递归关系，他只是在白板上写下它，并告诉我们它是“O(2^n)” 。起初，正如我之前所写的，我认为这是为了向我们展示归并排序递归关系和这个递归关系之间存在某种反直觉的东西。但当我后来询问时，情况变得清晰了。现在我真的很困惑他为什么要向我们展示这个。无论如何，你最后一句话很有趣，请您能详细解释一下吗？ - doplumi

Answer 3

您计算给定关系的时间复杂度是正确的。如果我们用n（这是应该的）来衡量输入大小，那么您的教授错误地声称时间复杂度是2^n。

您可能应该与他讨论并澄清您可能有的任何误解。

- pgiitu

---

我明天一定会做的。谢谢。 - doplumi