使用双 for 循环查找递归算法的时间复杂度

Question

我正在尝试为以下上限找到最严格的上限。但是，我无法得到正确的答案。算法如下：

public staticintrecursiveloopy(int n){
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.println("Hello.");
        }
    } if(n <= 2) {
        return 1;
    } else if(n % 2 == 0) {
        return(staticintrecursiveloopy(n+1));
    } else{
        return(staticintrecursiveloopy(n-2));
    }
}

我试图为此画出递归树。我知道对于算法的每个运行时间复杂度将是 O(n²) 加上每个递归调用所花费的时间。此外，递归树将有 n 层。然后我计算了每个级别花费的总时间：

第一关所用时间为n²。对于第二关，由于有两次递归调用，所以耗时为2n²。对于第三级，所用时间为4n ² 依此类推，直到n变为<= 2.

因此，时间复杂度应该是n² * (1 + 2 + 4 + .... + 2ⁿ) . 1 + 2 + 4 + .... + 2ⁿ是一个几何数列，其和等于2ⁿ - 1.Thus，总的时间复杂度应该是O(2ⁿn²)。然而，答案是 O(n³)。我做错了什么？

Answer 1

考虑以下片段

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        System.out.println("Hello.");
    }
}

这个不用介绍了，是O(n²)

现在考虑下面的片段

if(n <= 2) {
    return 1;
} else if(n % 2 == 0) {
    return(staticintrecursiveloopy(n+1));
} else {
    return(staticintrecursiveloopy(n-2));
}

你认为这个片段会被执行多少次？

如果n%2 == 0那么方法staticintrecursiveloopy将额外执行1次。否则它会将它减 2，因此它将被执行 n/2 次（如果包含其他条件，则执行 (n+1)/2）。

因此，方法 staticintrecursiveloopy 的执行总次数大约为 n/2，用复杂度表示时为 O(n)。

而方法staticintrecursiveloopy在每次迭代中调用复杂度为O(n²)的部分，因此总时间复杂度变为

O(n) * O(n²) = O(n³).

使用双 for 循环查找递归算法的时间复杂度

Finding the time complexity of a recursive algorithm with a double for loop

complexity-theory

time-complexity