确定从循环内部调用的递归函数的时间复杂度

Question

我不确定，之前是否在 SO 中问过这个问题。好吧，我正在检查数组中 char 的频率。我在确定复杂性方面相当薄弱，所以我认为这个社区可以帮助我明白这一点！如果我用一些抽象的方式发布它，我非常抱歉！如果有人可以帮助我，那就太好了！

这是我的代码：

class SearchAChar{
private static int getOccurance(char [] a, char k, int l, int r, int count){
    if(l == r) return count;

    if(a[l] == k){a[l]='0';count++;}

    return getOccurance(a, k, l+1, r, count);   
}
public static void main(String [] args){
    char [] arr = {'a', 'e', 'b', 'c', 'b', 'c', 'd','a'};

    for(int i=0; i<arr.length; i++){
        if(arr[i] == '0') continue;
        System.out.println("Occurance of : " +arr[i] + " is "+ getOccurance(arr, arr[i], i, arr.length, 0) +" times!");
    }
}
}

这个问题的运行时间复杂度应该是多少？？

Answer 1

由于有一个for循环，for循环内部有一个递归函数，其时间复杂度为运行O(n)，最差时间复杂度为O(n^2)其中 n 是 char 数组的长度。

Answer 2

让我们尝试分解；我说的是最坏情况下的复杂性。

n = length of the array

for(int i=0; i<arr.length; i++){} - 这不会循环 n 次，因为您通过在递归函数中将 seen char 设置为 0 来更新数组。如果 char 是 0 你继续。所以就像 O(n/2).
getOccurance(a, k, l+1, r, count) - 在每个字符上递归，直到长度 == 递增器。表示递归函数调用堆栈的最佳方式是作为树。例如，此图像显示了如何构建调用堆栈以计算斐波那契数列。

但是您的 getOccurance 函数不会像上面的斐波那契函数图片那样调用自身两次。所以我们可以说它在树的一个分支中有调用。换句话说，这里我们看到的调用栈序列是0,1,2... n-1，因此，我们可以计算复杂度O(n)。

如果我们将这两个步骤放在一起，我们就会得到。 O(n/2 * n)

但也正如@Coderino 提到的那样——在最坏的情况下性能不考虑非主导项。

综上所述，上述代码的复杂度为O(n^2)。

一些有用的资源 - https://users.cs.duke.edu/~ola/ap/recurrence.html

Complexity of recursive factorial program

确定从循环内部调用的递归函数的时间复杂度

Determining Time Complexity of a Recursive Function Calling From inside a Loop

java

algorithm

frequency

time-complexity