Java自定义sum方法的时间复杂度是O(n²)还是O(n³)？

public static double sum(double[] array)
{
   double sum = 0.0;
   for(int k = 0; k < size(array); k++)
       sum = sum + get(array, k);
   return sum;
}

public static double get(double[] array, int k)
{
   for(int x=0; x < k; x++)
       if(x==k) return array[k];
   return -1;
}

public static int size(double[] array)
{
   int size = 0;
   for(int k=0; k<array.length; k++)
       size++;
   return size;
}

结论 #

正确时间复杂度为O(n²)，你朋友的判断是对的。

详细推导 #

设输入数组array的长度为n，我们逐部分统计操作数：

1. size方法复杂度：每次调用会遍历完整数组统计长度，固定执行n次循环，单次调用时间复杂度O(n)。
2. get方法复杂度：循环条件为x < k，但循环内判断x==k永远不可能成立，所以每次调用固定执行k次循环，单次调用时间复杂度O(k)。
3. sum方法总操作数：
   • 外层for循环的条件判断每次执行前都会重新计算size(array)，从k=0到k=n共触发n+1次size调用，这部分总操作数为(n+1)*n = O(n²)。
   • 循环体共执行n次，k取值从0到n-1，对应get调用的总操作数为0+1+2+...+(n-1) = n(n-1)/2 = O(n²)。
   • 其余变量赋值、加法操作都是O(1)的常量操作，对复杂度无影响。
     总复杂度取最高阶的项，最终为O(n²)。

常见误区说明 #

你判断为O(n³)大概率是误将三层独立循环当成了嵌套结构，实际代码中并没有三层嵌套的执行逻辑，最高嵌套层数为2，所以最高阶项为n²。

内容的提问来源于stack exchange，提问作者Haardik Chopra