时间复杂度计算疑问：调用O(n)方法的O(n²)方法复杂度如何？

有个疑问：已知what方法的循环结构看起来是O(n²)，但它内部调用了时间复杂度为O(n)的f方法，那计算what的整体时间复杂度时，要不要把f的复杂度算进去？是变成O(n³)，还是各方法独立计算，what仍保持O(n²)？相关代码如下：

private static int f (int[]a, int low, int high)
{
    int res = 0;
    for (int i=low; i<=high; i++)
        res += a[i];
    return res;
}

public static int what (int []a)
{
    int temp = 0;
    for (int i=0; i<a.length; i++)
    {
        for (int j=i; j<a.length; j++)
        {
            int c = f(a, i, j);
            if (c%2 == 0)
            {
                if (j-i+1 > temp)
                    temp = j-i+1;
            }
        }
    }
    return temp;
}

分析与结论 #

• 先看f方法：它的循环次数等于high - low + 1，也就是传入的子数组长度，单次调用的时间复杂度是O(k)（k为当前子数组的长度），最坏情况为O(n)。
• 再看what方法的循环逻辑：外层i遍历数组每个元素，内层j从i开始遍历到数组末尾，每轮循环都会调用一次f。我们需要统计所有f调用的总执行步数：
  • 当i=0时，j从0到n-1，f的循环次数依次是1、2、...、n，总和为n(n+1)/2；
  • 当i=1时，j从1到n-1，f的循环次数依次是1、2、...、n-1，总和为(n-1)n/2；
  • ……
  • 当i=n-1时，j=n-1，f的循环次数是1。

把这些总和相加，最终结果为n(n+1)(n+2)/6，这个量级属于O(n³)。

所以必须把f的复杂度纳入考量，what方法的整体时间复杂度是O(n³)，而非O(n²)。因为时间复杂度计算的是整个方法的总执行步数，what里的双层循环只是执行了O(n²)次调用，但每次调用的f不是常数时间操作，而是线性时间，总步数是O(n²) * O(n) = O(n³)。

内容的提问来源于stack exchange，提问作者Dima Tkachuk