递归算法的复杂性

Question

我目前正在大学学习数据结构,偶然发现了一个关于递归复杂性的问题.

鉴于此代码:

Unsigned func (unsigned n)
{
 if (n ==0) return 1;
 if(n==1) return 2;

 \\do somthing(in O(1) )

 return func(n-1) + func(n-1);
} 

我知道代码的作用.我知道现在的形式是时间复杂度为O(2 ^ n).

然而,我的问题是:如果不是代码的最后一次返回调用,那么时间复杂度会改变return 2*func(n-1)吗？

我知道,就内存复杂性而言,我们谈论的是递归占用空间的显着减少,但就时间复杂度而言,是否会有任何变化？

我使用递归函数进行了数学运算,并且理解时间复杂度没有变化,我是对的吗？

Answer 1

这个方法只有O(n)，因为如果你用 5 运行它，它就会用 4 递归，然后用 3 等等。

Unsigned func (unsigned n)
{
 if (n ==0) return 1;
 if(n==1) return 2;

 \\do somthing(in O(1) )

 return 2*func(n-1);
}

然而这个又如何呢：

Unsigned func (unsigned n)
{
 if (n ==0) return 1;
 if(n==1) return 2;

 \\do somthing(in O(1) )

 return func(n-1) + func(n-1);
}

例如，在 func(5) 中，它将首先执行如下

5 -> 4 -> 3 -> 2 -> 1

然后它返回到2，但在那里它将执行“第二”部分，所以整个过程看起来像

5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.

因此，它确实将复杂性从 大幅改变O(n)为O(2^n)

让我们尝试一下这段代码的实际示例：

public class Complexity {
    private static int counter;
    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            counter = 0;
            func(i);
            System.out.println("For n="+i+" of 2*func the number of cycles is " + counter);
            counter = 0;
            func2(i);
            System.out.println("For n="+i+" of func + func the number of cycles is " + counter);
        }
    }

    public static int func(int n) {
        counter++;
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 2;
        }
        return 2 * func(n - 1);
    }

    public static int func2(int n) {
        counter++;
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 2;
        }
        return func2(n - 1) + func2(n - 1);
    }    
}

有这个输出：

For n=0 of 2*func the number of cycles is 1
For n=0 of func + func the number of cycles is 1
For n=1 of 2*func the number of cycles is 1
For n=1 of func + func the number of cycles is 1
For n=2 of 2*func the number of cycles is 2
For n=2 of func + func the number of cycles is 3
For n=3 of 2*func the number of cycles is 3
For n=3 of func + func the number of cycles is 7
For n=4 of 2*func the number of cycles is 4
For n=4 of func + func the number of cycles is 15
For n=5 of 2*func the number of cycles is 5
For n=5 of func + func the number of cycles is 31
For n=6 of 2*func the number of cycles is 6
For n=6 of func + func the number of cycles is 63
For n=7 of 2*func the number of cycles is 7
For n=7 of func + func the number of cycles is 127
For n=8 of 2*func the number of cycles is 8
For n=8 of func + func the number of cycles is 255
For n=9 of 2*func the number of cycles is 9
For n=9 of func + func the number of cycles is 511
For n=10 of 2*func the number of cycles is 10
For n=10 of func + func the number of cycles is 1023
For n=11 of 2*func the number of cycles is 11
For n=11 of func + func the number of cycles is 2047
For n=12 of 2*func the number of cycles is 12
For n=12 of func + func the number of cycles is 4095
For n=13 of 2*func the number of cycles is 13
For n=13 of func + func the number of cycles is 8191
For n=14 of 2*func the number of cycles is 14
For n=14 of func + func the number of cycles is 16383
For n=15 of 2*func the number of cycles is 15
For n=15 of func + func the number of cycles is 32767
For n=16 of 2*func the number of cycles is 16
For n=16 of func + func the number of cycles is 65535
For n=17 of 2*func the number of cycles is 17
For n=17 of func + func the number of cycles is 131071
For n=18 of 2*func the number of cycles is 18
For n=18 of func + func the number of cycles is 262143
For n=19 of 2*func the number of cycles is 19
For n=19 of func + func the number of cycles is 524287

但如果您还记得已经计算出的结果，那么复杂性仍然O(n)与第二种方法相同：

public class Complexity {
    private static int counter;
    private static int[] results;

    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            counter = 0;
            func(i);
            System.out.println("For n="+i+" of 2*func the number of cycles is " + counter);
            counter = 0;
            func2(i);
            System.out.println("For n="+i+" of func + func the number of cycles is " + counter);
            counter = 0;
            results = new int[i+1];
            func3(i);
            System.out.println("For n="+i+" of func + func with remembering the number of cycles is " + counter);
        }
    }

    public static int func(int n) {
        counter++;
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 2;
        }
        return 2 * func(n - 1);
    }

    public static int func2(int n) {
        counter++;
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 2;
        }        
        return func2(n - 1) + func2(n - 1);
    }

    public static int func3(int n) {
        counter++;
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 2;
        }

        if (results[n] == 0){
            results[n] = func3(n - 1) + func3(n - 1);
        }

        return results[n];
    }        
}

有这个输出：

For n=0 of 2*func the number of cycles is 1
For n=0 of func + func the number of cycles is 1
For n=0 of func + func with remembering the number of cycles is 1
For n=1 of 2*func the number of cycles is 1
For n=1 of func + func the number of cycles is 1
For n=1 of func + func with remembering the number of cycles is 1
For n=2 of 2*func the number of cycles is 2
For n=2 of func + func the number of cycles is 3
For n=2 of func + func with remembering the number of cycles is 3
For n=3 of 2*func the number of cycles is 3
For n=3 of func + func the number of cycles is 7
For n=3 of func + func with remembering the number of cycles is 5
For n=4 of 2*func the number of cycles is 4
For n=4 of func + func the number of cycles is 15
For n=4 of func + func with remembering the number of cycles is 7
For n=5 of 2*func the number of cycles is 5
For n=5 of func + func the number of cycles is 31
For n=5 of func + func with remembering the number of cycles is 9
For n=6 of 2*func the number of cycles is 6
For n=6 of func + func the number of cycles is 63
For n=6 of func + func with remembering the number of cycles is 11
For n=7 of 2*func the number of cycles is 7
For n=7 of func + func the number of cycles is 127
For n=7 of func + func with remembering the number of cycles is 13
For n=8 of 2*func the number of cycles is 8
For n=8 of func + func the number of cycles is 255
For n=8 of func + func with remembering the number of cycles is 15
For n=9 of 2*func the number of cycles is 9
For n=9 of func + func the number of cycles is 511
For n=9 of func + func with remembering the number of cycles is 17
For n=10 of 2*func the number of cycles is 10
For n=10 of func + func the number of cycles is 1023
For n=10 of func + func with remembering the number of cycles is 19
For n=11 of 2*func the number of cycles is 11
For n=11 of func + func the number of cycles is 2047
For n=11 of func + func with remembering the number of cycles is 21
For n=12 of 2*func the number of cycles is 12
For n=12 of func + func the number of cycles is 4095
For n=12 of func + func with remembering the number of cycles is 23
For n=13 of 2*func the number of cycles is 13
For n=13 of func + func the number of cycles is 8191
For n=13 of func + func with remembering the number of cycles is 25
For n=14 of 2*func the number of cycles is 14
For n=14 of func + func the number of cycles is 16383
For n=14 of func + func with remembering the number of cycles is 27
For n=15 of 2*func the number of cycles is 15
For n=15 of func + func the number of cycles is 32767
For n=15 of func + func with remembering the number of cycles is 29
For n=16 of 2*func the number of cycles is 16
For n=16 of func + func the number of cycles is 65535
For n=16 of func + func with remembering the number of cycles is 31
For n=17 of 2*func the number of cycles is 17
For n=17 of func + func the number of cycles is 131071
For n=17 of func + func with remembering the number of cycles is 33
For n=18 of 2*func the number of cycles is 18
For n=18 of func + func the number of cycles is 262143
For n=18 of func + func with remembering the number of cycles is 35
For n=19 of 2*func the number of cycles is 19
For n=19 of func + func the number of cycles is 524287
For n=19 of func + func with remembering the number of cycles is 37