Java for循环的时间复杂度

Question

我已经开始学习大O符号和分析时间复杂性，我试着摆弄一些代码，试图理解它的时间复杂性。这是我写过的其中一行，但我不知道求和方法的时间复杂度是多少?我估计是0 (n^3)但我朋友说应该是0 (n^2)对正确答案有什么见解吗?

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;

}

Answer 1

我想你的朋友是对的，时间复杂度是O(n^2)。因为在循环中的每次迭代中，您都会计算size()，这是O(n)的阶数，并计算get()，这平均是O(n/2)。所以每次迭代的复杂度是O(1.5 * n)，总的复杂度是O(n^2)