java - 功能的大O表示法

Question

以下函数将大小为n的一维数组A作为参数，并返回大小为n x n的2D数组M。 M存储平均值。如果i <= j，则使用公式M [i] [j] =（A [i] + ... + A [j]）/（2），从数组A的两个迭代变量（i an j）之间计算这些平均值。 j-i + 1）。例如，如果i = 1，而j = 3。然后M [0] [3]将存储根据M [1] [3] =（A [1] + A [2] + A [3]）/ 3-1 + 1计算得出的值

 public float[][] averageArray(float[] A){
        int n = A.length;
        float sum;
        float[][] M = new float[n][n];

        for(int j = 0; j<n;j++){
            for(int i = 0; i<n; i++){

                if(i<=j) {
                    sum = 0;
                    for (int k = i; k <= j; k++) {
                        sum += A[k];

                    }
                    M[i][j] = sum / (j - i + 1);
                }else{
                    M[i][j] = 0;
                }

                System.out.println("["+ i +"]" + "["+ j +"]: "+ M[i][j]);
            }

        }
        return M;
    }

我对该功能的大符号感到困惑。我知道前两个for循环会产生O（n ^ 2）的big-O，但是由于第三个循环是有条件的，因此我不确定如何将其放入big-O表示法中。从测试中，我发现执行第三个循环的次数随j值的增加而增加（例如，如果j = 3，则循环执行3次，如果j = 5，则循环将执行5次）。

Answer 1

tl; dr，当您不确定它如何影响big-o运行时时，请为循环创建一个求和，然后将该求和转换为n的函数

有时您会遇到诸如“最里面的循环中的行以n表示执行了多少次这样的问题。这不完全是运行时分析，但是这里是一种分析。它将帮助您更好地了解big-o运行。

将计数器放在内部循环中并查看其执行次数可能会有所帮助。

绘制网格并为正方形着色可能也是有帮助的，其中i <= j和j是行索引（因为它是第一个循环的变量），而i是列索引）。执行此操作时，您会看到所有彩色正方形将对角线从左上角到右下角将对角线网格分成2个三角形。任何直接落在行中的内容仍然有效（因为您说的是<=而不是<）。彩色的正方形将是底部/左侧的三角形。

这只是最里面的循环实际上将在其中执行某项操作的描述。

现在，外部2个循环将遍历网格中的每个位置。我们将其称为当前位置。现在，每次由外部2个循环确定新位置时，内部循环中的一行代码将对网格该列中当前位置上方的每个彩色正方形执行一次（如果已着色，则对当前位置执行一次）。

可视化后，您可以更轻松地查看如何计算此操作的执行次数。网格的第一列有n个彩色正方形。第一次计算该列是在选择左上角的正方形时（j = 0，i = 0）。第二次是（j = 1，i = 0）。因此，让我们填写一个网格，其中每个位置的值是每个单元格被计数的次数。它将是这样的：

[n,  0 ,  0,  0, ... ]
[n-1, n-1, 0, 0, ... ]
[n-2, n-2, n-2, 0, ...]

您现在可以看到图片。现在，将这个网格中的所有内容加起来将告诉您最内层的循环执行了多少次。


第一行有1 n
第二行有2（n-1）个
第三行有3（n-2）个


您可以看到（n-j）*（j + 1）的模式作为每一行的总数。

对各行求和以获得总计。

您最终得到的是这样的：

for(int i = 0; i < n; i++)
    sum += (n-i)*(i+1);
return sum;

这只是最内层循环执行的次数。现在，最内层的循环没有执行。这部分要容易得多。这只是先前网格中非彩色正方形的数量。

因为它是一个n×n的网格，所以n2 / 2似乎是正确的答案。但是主要的对角线正方形都是彩色的。 n2 / 2已经占该行的一半，因此我们必须取出另一半：n / 2。

因此，执行的总次数将是上面的for循环总和，再加上n的平方的一半（非彩色正方形），减去n的一半（因为您刚刚将对角线的一半加了上一个加上字词）。

最终看起来像

前两个术语的含义是最里面的for循环未执行的次数。

当我运行此代码时，结果如下：


n = 10


内循环执行：220
处决总数：265
220 + 102/2-10/2（220 + 50-5 = 265）

n = 100


内循环执行：171700
处决总数：176650

n = 1000


内循环执行：167167000
处决总数：167666500

n = 10000


内循环执行次数：166716670000
处决总数：166766665000

n = 100000


内循环执行次数：166671666700000
处决总数：166676666650000

n = 100000000（仅用于哈尔兹，您已经可以看到该模式）


内循环执行：166666671666666700000000
处决总数：166666676666666650000000



对于我的最终启示，因为您已经阅读了此文件
这是一个O（n3）函数。

我不会过多介绍它，但是最里面的for循环执行的次数的总和简化为

将最内层循环未执行的次数相加的2个项相加，对类似项进行分组以简化，您将得到以下结果：



您可以使用这最后2个公式来验证我上面共享的数据。您还可以通过在循环中添加计数器并运行它们以查看它们执行了多少次并将其与这些公式给出的值进行比较来进行经验验证（对于与我提供的值一样大的值，您需要使用BigInteger s或其他任意大数字格式）。如果您不信任我或您的计算机，也可以尝试在解决方程式的在线工具（例如Wolfram alpha）上投入一些此类信息。最后，如果这是来自考试题，则可以带给您的教授，展示该问题的性质，并且给出给定for-loop的n确切执行次数是数组A的长度。如果所有这些都是错误的，那么我至少已证明它对于10的幂是正确的。希望这会有所帮助。