递归方法的大O

Question

我很难确定简单递归方法的大 O。我如何为这些方法计算大 O？

案例 1) 为方法 f 找到大 O:

int f(int x){
    if(x<1) return 1;
    return f(x-1)+g(x);
}

int g(int x){
    if(x<2) return 1;
    return f(x-1)+g(x/2);
}

案例二)

int test(int n){
    if(x<=2) return 1;
    return test(n-2) * test(n-2);
}

案例三)

int T(int n){
    if(n<=1) return 1;
    return T(n/2)+T(n/2);
}

Answer 1

案例一

抛开基本情况（g(1) = g(0) = 1 等），您可以根据 f:

重写 g

f(n) = f(n-1) + g(n) <=> g(n) = f(n)-f(n-1)

我们知道g定义为：

g(n) = f(n-1) + g(n/2)

如果我们用上面重写的形式替换g(n/2)，我们得到：

g(n) = f(n-1) + f(n/2) + f(n/2-1)

这意味着我们可以在不引用g的情况下重写f，方法是将f的原始定义中的g(n)替换为上面的公式：

f(n) = f(n-1) + f(n-1) + f(n/2) + f(n/2-1)

要仔细检查这是否等效，您可以运行这个程序，它接受一个整数 n 作为第一个参数，然后打印原始 f(n) 的结果通过 f(n) 的重写形式（在代码中称为 f2）：

#include <stdio.h>

int g(int x);

int f(int x) {
    if (x < 1)
        return 1;
    return f(x-1)+g(x);
}

int g(int x) {
    if (x < 2)
        return 1;
    return f(x-1)+g(x/2);
}

int f2(int x) {
    if (x < 1)
        return 1;
    return f2(x-1)+f2(x-1)+f2(x/2)-f2(x/2-1);
}

int main(int argc, char *argv[]) {
    int n;
    sscanf(argv[1], "%d", &n);
    printf("%d\n", f(n));
    printf("%d\n", f2(n));
    return 0;
}

一些例子：

$ ./a.out 10
1952
1952
$ ./a.out 11
3932
3932
$ ./a.out 12
7923
7923
$ ./a.out 13
15905
15905
$ ./a.out 14
31928
31928
$ ./a.out 15
63974
63974

现在，如果您想象递归树，每个节点分支成 4 个子树（f(n-1)、f(n-1)、f(n/2) 和 f(n/2-1)).每个子树的大小是不一样的，例如，如果我们下降到一个子树并且总是跟随两个最右边的分支中的任何一个，我们就有一个深度为 log(N) 的二叉树。但是还有其他分支（如果我们始终遵循 f(n-1) 路径）具有深度 n，并且它分支到 n-1 两次。因此，我们可以说它绝对是指数级的。

很难得到确切的数字，但一个明显的上限是 O(4^N) - 虽然这忽略了一些分支只有 log(N) 深的事实，所以实际上它有点优于 O(4^N).

案例二

再想想递归树。在每个点，我们分支两次（test(n-2) 和 test(n-2)）。因为我们在每次调用时将 n 减少 2，所以树将是 O(n/2) 深，所以我们需要 O(2^(n/2)) 时间来遍历树 - 同样，指数增长。不是特别有趣。

（旁注：如果你在这里使用记忆，这将是线性的！）。

案例三

与情况 2 类似的逻辑，但这次树的深度为 log(N)（因为这是您需要将 N 除以 2 的次数才能得到基本情况），所以我们得到 2^log(N) = N。所以它是线性的。

递归方法的大O

Big O of Recursive Methods

recursion

big-o