java - 算法的时间复杂度

Question

我创建了两种算法来计算给定数组的前缀平均值。我想推导出这两种算法的时间复杂度，但我一直在努力。我看了这个 YouTube 视频: https://www.youtube.com/watch?v=udwxWq9wZgg&safe=active .我不明白如何计算 for 循环和嵌套 for 循环中的操作数。

在 2 点 27 分，我成功地统计了 PrefixAverages2 中 for 循环中的操作。是 3n+1。但是，从 5:50 开始我就听不懂了。

提前致谢。

public double[] PrefixAverages1(double input[])
{
    double A[] = new double[input.length];
    double s;


    for(int i=0; i <= input.length - 1 ;i++)
    {
        s = input[0];

        for(int j=1; j <= i ;j++)
        {
            s = s + input[j];
        }

        A[i] = s / (i+1);
    }


    return A;  

}





public double[] PrefixAverages2(double input[])
{
    double A[] = new double[input.length];
    double s = 0;

    for( int i=0; i <= input.length - 1 ; i++)
    {
        s = s + input[i];
        A[i] = s / (i+1);

    }

    return A;  

}

Answer 1

   for(int i=0; i <= input.length - 1 ;i++)
        for(int j=1; j <= i ;j++)

这是二次方的，对于给定的 i，内部循环大约进行 i 次，所以你必须对 i 求和，所以基本上你有类似 sum_{i=1}^{i=l} i 的东西，它是前 l 个整数的和，即 l(l+1)/2，然后是二次方。

对于第二种算法，您只有一个循环，因此它的复杂度是线性的。