递归函数内调用substr的整体时间复杂度是否为O(n²)？

在如下所示的函数中，substr()的时间复杂度为O(n)，该方法在递归函数内部调用，且递归调用的时间复杂度为O(n)，那么整个代码块的时间复杂度是否为O(n²)？

void replacePi(string s) {
    if(s.length() == 0) {       // base case
        return;
    }
    if(s[0] == 'p' && s[1] == 'i') {
        cout << "3.14";
        string remaining = s.substr(2); //remaining substring
        replacePi(remaining);
    } else {
        cout << s[0];
        replacePi(s.substr(1));
    }
}

结论 #

答案是肯定的，这段代码的最坏时间复杂度确实为O(n²)。

推导过程 #

• 先统计递归总次数：不管每次匹配到pi跳过2个字符，还是没匹配到跳过1个字符，递归的总次数最多为n次（n为原始字符串的长度，对应字符串中完全没有pi组合的场景）。
• 每次递归都会调用substr()方法生成新的子串，题目已经给出substr()的时间复杂度是O(k)，其中k是截取的子串长度。
• 最坏情况（无pi组合）下，每次递归截取的子串长度依次是n-1、n-2、...、1，所有substr()操作的总时间开销为：

  (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2
  

  属于*O(n²)的量级，其他操作（判断字符、输出）都是O(1)*的量级，不会改变整体时间复杂度。

优化建议 #

如果要把时间复杂度降到O(n)，可以不用每次生成新的子串，额外传递一个当前遍历的下标参数，直接在原始字符串上操作即可，避免字符串复制的额外开销。

内容的提问来源于stack exchange，提问作者Pranab Das