java - 查找此递归函数的时间复杂度

Question

这个算法有点废话，因为我把它简化成了基本方案。

基本上，它以一个字符串作为输入，扫描这个字符串并创建一个不包含旧字符串首字母的新字符串。那是一个 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);
    }}

Answer 1

它实际上比 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).