c - 确定特定功能的时间复杂度

Question

这是我最近遇到的关于算法和数据结构的旧考试中的一个问题。我很难理解该解决方案。
我需要找到函数的big-O，big-ϴ和big-Ω范围:

void recursion(int n) {
 int i;
 if (n == 0) {
 return;
 }
 for (i = 0; i < n; i++) {
 recursion(i);
 }
}

解决方案是所有这三个的2^n，我不明白为什么。我试图写下来的东西，甚至无法接近解决方案。如果有人能解释2^n的来源，我将不胜感激。

Answer 1

让我们看一个更简单的递归，它称为O(2 ^ n)

void fib(int n) {
    if (n < 3) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

在这里您可以看到，对于n> 2的非平凡情况，这将导致对自身的2 ^(n-2)个调用。例如，如果n = 5:

n = 5
    n = 4
        n = 3
            n = 2
            n = 1
        n = 2
    n = 3
        n = 2
        n = 1

有8(2 ^ 3)个递归调用，因为n> 2的每个调用会产生两个递归调用，因此fib(n + 1)的递归调用数量是fib(n)的两倍。

因此，对于您的示例:

n = 3
    n = 2
        n = 1
            n = 0
        n = 0
    n = 1
        n = 0
    n = 0

所以当n = 3时我们得到7个递归调用

对于n = 4

n = 4
    n = 3
        n = 2
            n = 1
                n = 0
            n = 0
        n = 1
            n = 0
        n = 0
    n = 2
        n = 1
            n = 0
        n = 0
    n = 1
        n = 0
    n = 0

在这里，我们有15个电话。查看上面的执行树，您可以看到reusrsion(4)本质上是recursion(3)+ recursion(3)+1

n = 4
    n = 3          // + 1
        n = 2                //
            n = 1            //
                n = 0        // recursion(3)
            n = 0            //
        n = 1                //
            n = 0            //
        n = 0                //
    n = 2           //
        n = 1       //
            n = 0   // recursion(3)
        n = 0       //
    n = 1           //
        n = 0       //
    n = 0           //

因此，一般而言，递归(n + 1)的递归调用要比2 *递归(n).....基本上每+1到n都加倍....即O(2 ^ n)