这个递归算法的大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==

替换后，我们获得

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

由于该算法是从关于合并排序的课程中跳出来的，所以我注意到了如何进行合并排序，这是出了名的O（n log n）

我的问题是：

1. 我的论证有什么谬误吗

是的，这也是一个通风口。

Answer 1

很明显，满足递归关系的函数是O（n），这是正确的。这是显而易见的，因为它说，一个给定问题的复杂性是一个大小为一半的问题的两倍。你不可能得到比这更多的线性。例如，使用线性搜索搜索包含1000个元素的列表的复杂性是搜索包含500个元素的列表的复杂性的两倍。

如果您的教授也是正确的，那么您可能对满足该递归的复杂性不正确。或者，有时对如何测量输入大小存在一些混淆。例如，整数n在指定它所需的位数上是指数的。例如——整数n的蛮力试除法是O（sqrt（n）），这比O（n）好得多。这与蛮力分解对于例如破解RSA基本上毫无价值的事实并不矛盾的原因是，对于256位密钥，相关的n大约是2^256。

Answer 2

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

你可能应该和他讨论一下，消除你可能存在的误解。

Answer 3

证明-1

这个递归属于主定理的情况-3，具有

• a=2
• b=2；和，
• c=-∞

因此Log_{ba=1，大于-∞. 因此，运行时间为Θ（n¹）=Θ（n）。}

证明-2

直观地说，您正在将大小为n的问题分解为大小为n/2的两个问题，并且将两个子问题的结果合并的成本为0（即，在循环中没有常数分量）。

因此，在最底层，您有n个成本为1的问题，导致n*O（1）的运行时间等于O（n）。

编辑：为了完成此答案，我还将为您提出的特定问题添加答案。

我的论证有谬误吗？

不，这是正确的。

最后一种情况不是违反直觉吗？

这绝对是违反直觉的。参见上面的证明-2。