递归函数的时间复杂度

Question

我的数据结构和算法课程的老师在课堂上介绍了如何求递归函数的时间复杂度，直到他给出了这两个例子，我才明白了一些内容：

示例1

function compute_polynomial_recursive(x, n):
    if n == 1:
        return x 
    else:
        return (x[n]^3) + compute_polynomial_recursive(x, n - 1) 

时间复杂度：O(n)

示例2

function compute_polynomial_recursive(a, n):
    if n == 1:
        return a^1 
    else
        return (a^n) + compute_polynomial_recursive(a, n - 1) 

时间复杂度是多少？

b) 解决方案

T(n) = T(n-1) + O(n)

替代品：

T(n-1) = T(n-2) + O(n-1)

T(n) = T(n-2) + O(n-1) + O(n)

      = T(1) + O(2) + O(3) + … + O(n-1) + O(n)

      = (n+1)n/2

      = O(n^2)

c) 使用归纳法

假设对于任意n，时间复杂度为O(n^2)。

尝试证明对于n+1，时间复杂度为O((n+1)^2)，即O(n^2)。

也许我很愚蠢，但与我交谈的其他人也很困惑。有人能解释为什么其中一个函数是 O(n^2) 而另一个是 O(n) 吗？

Answer 1

什么是时间复杂度？

给定一个具有一些输入的算法，我们想知道根据输入的“某些”特征需要多少时间。通常我们对输入的大小感兴趣，但在人工示例中，我们经常看到显式输入参数n。

那么，给定的

n

需要多少时间？不可能说清楚。我们的算法可能运行在更快或更慢的处理器上，代码可能是用好或坏的编译器编译的，等等。为了得到“一些”答案，我们作弊：我们认为算法中的每个操作都需要一个或多个“单位”/“步骤”时间并计算这些时间。 “数组”数据结构的一个重要特征是元素访问具有恒定的成本：

T("x[n]") = const

。例如，对于某些假设的算法，总时间可能是 T(n) = n^3 + 11n^2 - 4。此外，我们需要它来描述和比较算法，并且如果我们进行一些“微小”修改，我们的估计也不会改变。事实证明，将“精确”函数四舍五入到它们的

Big-O类

往往可以解决这两个问题（除了在编程中我们经常希望将所有

O(a^n)

类“粘合”成一个，称为“增长太快而无法实用”）。 我们如何计算时间复杂度？

我们从算法组成的一些基本动作的“价格”开始，然后将它们加在一起。大多数时候，我们认为使用单个运算符符号编写的任何操作的成本为 1 个单位。然而，在你的情况下，你的老师

似乎

暗示

a^n

的成本在O(n)中。我假设它是

n-1

。每个功能也都有价格。因此，我们通常可以读取函数并写出方程：

function compute_polynomial_recursive(x, n):
    if n == 1:
        return x 
    else:
        return (x[n]^3) + compute_polynomial_recursive(x, n - 1)

T(1) = 2

； 

T(n) = 1 + 1 + (3-1) + 1 + T(n-1) + 1 + 1 | n>1

。 （我将

return

计算为时间损失，但函数调用为“自由”。）给定这些方程，很容易获得

T(n)

的“封闭形式”表达式：

T(n) = 7 + T(n-1) = 7 + 7 + T(n-2) = ... = 7*(n-1) + T(1) = 7n-5

。一旦你获得了它，你也可以写O级：

T(n) = O(n)

。

在第二个示例中，我们有一个更棘手的表达式。

function compute_polynomial_recursive(a, n):
    if n == 1:
        return a^1 
    else
        return (a^n) + compute_polynomial_recursive(a, n - 1) 

T(1) = 2

； 

T(n) = 1 + (n-1) + 1 + T(n-1) + 1 + 1 = (n+3) + T(n-1)

。再次，我们可以简单地折叠表达式：

T(n) = (n+3) + ((n-1)+3) + ... + (2+3) + 2 = n^2/2 + 7n/2 - 2

（自查：

T(1)

仍然是

2

）。用大 O 符号表示，

T(n) = O(n^2)

。直观上，这一次第一次调用的工作量随着

n

的增加而增长，因此整个计算速度变慢。（在这两种情况下，这些都是不好的递归：您通常希望函数调用是

return

之前的最后一条指令，但这与

内存

复杂性有关：编写的这些函数很容易耗尽堆栈空间.)

我们可以跳过这个“计算每个操作”的混乱吗？ 有点。您

可以

仅跟踪 O 类 - 在这种情况下，对于每个连续操作字符串，您只需要考虑其中渐近最慢的操作。但您需要注意不同被加数中省略的乘数是相同的（或者至少不能增长任意大）：

n + 2*(n-1) + 3*(n-2) + 4*(n-3) + ... = O(n) + O(n-1) + O(n-2) + ... = O(n^2)

但如果你明确地将总和写为 n 的函数，结果就是

O(n^3)

。哎呀？在您确信自己可以观察到这些表达式之前，我建议您至少尝试写下“准确”的时间。从某种意义上说，这也是实用的，无论如何，在真正的优化中，你需要注意那些“不变”的因素。我们可以使用感应吗？

是的，但绝对不是如示例所示。

function F(n):
    if n == 1:
        return 1;
    else
        return 1 + F(n);

“推理”：假设

T(n) = O(n^3)

。然后 

T(n+1) = 2 + T(n) + 1 = O(n^3) + 3 = O((n+1)^3)

（因为

O(n^3)

和

O((n+1)^3)

是同一类）。因此，

T(n) = O(n^3)

。真实推理：假设

T(n) = O(n^3) = k*n^3 + o(n^3)

（注意

小

o！）。那么我们需要证明这一点

T(n+1) = k'*(n+1)^3 + o((n+1)^3

。我们尝试 - T(n+1) = 2 + T(n) + 1 = k*n^3 + 3 + o(n^3) ≠ k'*(n+1)^3 + o((n+1)^3) - 但我们失败了。另一方面，假设

T(n) = O(n)

成功：

T(n+1) = k*n + 3 + o(n) = k*(n+1) + (3-k) + o(n) = k*(n+1) + o(n+1)

。