递归调用的时间复杂度

Question

我编写了一段代码来递归地从字符串中删除相邻的重复项

class Solution{
String rremove(String s) {
    // code here
    
    StringBuilder sb = new StringBuilder();
    int i = 0;
    
    while (i < s.length()) {
        char currentChar = s.charAt(i);
        int j = i + 1;
        // Find the index of the next different character
        while (j < s.length() && s.charAt(j) == currentChar) {
            j++;
        }
        // If adjacent duplicates found, skip them
        if (j - i > 1) {
            i = j;
        } else {
            sb.append(currentChar);
            i++;
        }
    }
    
    String result = sb.toString();
    // If result string is different from original, recursively call the function
    if (!result.equals(s)) {
        return rremove(result);
    }
    return result;
    
}

现在，我想了解这段代码的时间复杂度，因为这里的递归调用次数不是固定的，因此在查看代码时感到非常困惑。虽然，每个方法调用都是O(n)，但是随着递归的深度，它变得不确定。因此，请帮助我了解此代码的最佳情况和最坏情况。

代码来自 GFG，标题为“递归删除所有相邻重复项”

Answer 1

如果我们从分析中排除递归调用，复杂度确实是 O(𝑛)。这也是时间复杂度最好的情况，即由于输入中不存在相邻重复而未进行递归调用时。

当我们合并递归调用时，最坏的情况会发生在回文数中，唯一的重复字符出现在中心。例如

abababababbababababa

。现在我们调用

rremove

，得到长度为 𝑛 的字符串，然后是 𝑛−2, 𝑛−4, ... 2, 0.

所以最坏情况的时间复杂度是 O(𝑛²)。