我不确定,之前是否在 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!");
}
}
}
这个问题的运行时复杂度应该是多少??
最佳答案
由于有一个 for 循环并且在 for 循环内部有一个递归函数,其运行时复杂度为 O(n),这使得最坏的时间复杂度为 O(n^2),其中 n 是字符数组。
关于java - 确定从循环内部调用的递归函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54804773/