递归函数的 Theta 时间复杂度

Question

查找以下代码片段的 Theta 顺序运行时给我带来了麻烦：

void foo(int n)
{
    if (n <= 1)
    {
        return;
    }

    for(i = 0; i < n; i++)
    {
        cout << endl;
    }

    foo(n / 2);
    foo(n / 2);
}

if语句是Θ(1)。 for 循环是 Θ(n)。在我看来，递归函数调用是 Θ(log n)。我的理解是，我会将 Thetas 加起来，最高阶 (Θ(n)) 将保留下来，并且代码段是阶 Θ(n)。我的理解正确吗？

Answer 1

好的，这是对正在发生的事情的正确解释。时间复杂度为 Θ(n log n).

首先需要注意的是我们正在使用嵌套循环。（递归是编写循环的另一种方式。）

这意味着我们的复杂度函数看起来像 n×k。为方便起见，我们将 n 视为 元素数量 ，将 k 视为 递归深度 。举个例子：

1 2 3 4 5 6 7 8  ← number of elements
---------------  1st pass
------- -------  2nd pass
--- --- --- ---  3rd pass
- - - - - - - -  4th pass ← recursion depth

second 需要注意的是，每次调用该函数时，数组的每个 元素都会被触及。我们触摸所有 n 第一关。然后我们递归 n/2 和 n/2，但同样所有 n 都被触及。对每个递归级别重复 - 所有 n 都被触及。¹

^{¹ 差不多。尝试为 10 个元素绘制示例。您会看到在 final 遍中未触及某些元素。不要让这个打扰你......我们稍后会重新讨论为什么。}

第三个要注意的是递归深度不同于元素的数量。即k≠n!

一开始您可能会想到 8 : 4 → 二分之一，但尝试绘制一个包含 16 个元素的示例：我们发现比例现在是 16 : 4 → 四分之一。 12个元素怎么样？ 12 : 4（一 三分之一？）。 17-32 个元素怎么样？是的：17–32 : 5（wut？）。

您应该立即将其识别为以 2 为底的对数级数。（请记住，对数是求幂的数学倒数。）原始函数具有对数 base of 2（因为我们每次调用递归两次，一次遍历数组当前部分的每一半）。它是对数的，因为它缩小了我们的递归深度而不是增加了它。


⌈log₂ 8⌉ →	⌈3⌉ →	3	2³ = 8
⌈log₂ 10⌉ →	⌈3.32⌉ →	4	2³⋅³² = 10
⌈log₂ 12⌉ →	⌈3.58⌉ →	4	...
⌈log₂ 16⌉ →	⌈4⌉ →	4	...

它是一个ceiling函数，因为递归深度是一个整数。（你不能有点递归，有点。你要么做了要么没有。）²

因此，k=log₂n.

^{² 这是关于为什么我们不关心最终传球是否完美的难题的第二部分……不过，我们还没有完成。}

我们现在可以把它放在一起了。我们的复杂度函数是 f(n) → n log₂n.

因为算法在最差情况下（O(n log n)）和最好情况下（Ω(n log n))，我们现在也有它的紧界：Θ(n log n).

复杂性符号会丢弃无关紧要的内容。我们不关心 实际的 复杂度是否类似于 n + 2 因为随着 n 变大（“趋向于无穷大”，或者对于我们程序员来说，趋向于几个十万）+2 是没有意义的，就像我们是否真的在最后一次通过所有 n 个元素一样。³

同理可以折腾出对数的底数。这最终并不重要。您所需要的只是具有最高功率的术语，并且您已经足够好了。例如，O(2n² + 4n - 3)→O(n²)，因为n越大，n²就占主导地位。

^{³ 哈，到了！}

其中很多内容需要熟悉。我们还可以看到，即使有一段时间（尤其是 sleep-deprived）没有想过这些想法的经验丰富的开发人员也会犯非常非常愚蠢的错误，就像我第一次用 O(n²) 轻松回答时所做的那样.

抱歉，我花了这么长时间才想到我想为大家说这句话。随着时间的推移，思考这些事情确实变得容易一些（并且不断重复，哈哈）。

递归函数的 Theta 时间复杂度

Theta time complexity of a recursive function

big-o

time-complexity