这个算法有点废话,因为我把它简化成了基本方案。
基本上,它以一个字符串作为输入,扫描这个字符串并创建一个不包含旧字符串首字母的新字符串。 那是一个 O(n^2) 吗?如果你能证明答案是正确的。谢谢。
recursiveProc(String myString){
if(myString.length() >= 1){
char firstLetter = myString.charAt(0);
String newString = "";
for(int i = 0; i < myString.length(); i++){
if(myString.charAt(i) != firstLetter){
newString = newString + myString.charAt(i);
}
}
recursiveProc(newString);
}}
最佳答案
它实际上比 O(N^2)
还差。看起来像 O(N^3)
。
每次递归调用都会将输入的 String
减少至少一个字符,因此最多会有 N
次递归调用(在最坏的情况下恰好有 N
次递归调用,每次都将输入的 String
减少一个字符)。
但是,您的循环需要 O(N^2)
,因为它有 O(N)
次迭代,并且每次迭代都会创建一个新的 String
其长度不是常量。
假设您有字符串“0123456789”
第一个递归调用将通过创建以下 String
删除“0”字符:
"1"
"12"
"123"
"1234"
"12345"
"123456"
"1234567"
"12345678"
"123456789"
这将花费 O(N^2)
时间。这只是第一个递归调用。
您可以通过使用 StringBuilder
而不是 String
连接来创建新的 String
来改进它。
StringBuilder sb = new StringBuilder(myString.length()-1);
for(int i = 0; i < myString.length(); i++){
if(myString.charAt(i) != firstLetter){
sb.append(myString.charAt(i));
}
}
recursiveProc(sb.toString());
在这种情况下,循环将耗时 O(N)
(因为循环的每次迭代都在不断地工作)并且整个递归将耗时 O(N^2)
.
关于java - 查找此递归函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51742907/