下面的函数将大小为n的一维数组a作为参数，并返回大小为nxn的二维数组m。m存储平均值。如果i<=j，则使用公式m[i][j]=（a[i]+…+a[j]）/（j-i+1）从两个迭代变量（i和j）之间的数组a计算这些平均值。例如，如果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;
}我对这个函数的big-o表示法感到困惑。我知道前两个for循环产生一个o（n^2）的big-o，但是因为第三个循环是有条件的，所以我不知道如何把它转换成big-o表示法。通过测试，我发现第三个循环的执行次数随着j值的增加而增加（例如，如果j=3，则循环执行3次，如果j=5，则循环执行5次）。
2条答案
按热度按时间8nuwlpux1#
热释光；dr如果您不确定它是如何影响big-o运行时的，请为循环创建一个求和，然后将该求和转换为的函数
n有时您会遇到这样的问题：“以n表示，最内部循环中的行执行了多少次。这不完全是运行时分析，但这里仍然有一个分析。它将帮助您更好地了解big-o运行时。在内部循环中放置一个计数器并查看它执行了多少次可能会有所帮助。
它也可能有助于绘制一个网格和颜色的广场上
i <= j以及j是行索引（因为它是第一个循环的变量），并且i是列索引）。当你这样做的时候，你会看到所有的彩色正方形把正方形网格从左上到右下沿对角线分成两个三角形。任何直接落在这条线上的东西都很重要（因为你说过<=而不是<). 彩色正方形将是底部/左侧三角形。这只是描述了最里面的循环将实际执行某些操作的位置。
外部2个循环现在将在网格中的每个位置上迭代。我们称之为当前位置。现在，每当外部2个循环确定一个新位置时，内部循环中的一行代码将对网格列中当前位置上方的每个彩色正方形执行一次（如果当前位置是彩色的，则执行一次）。
在可视化之后，您可以更容易地看到如何计算它将执行的次数。网格的第一列有n个彩色正方形。此列第一次计数将在选择左上角的正方形（j=0，i=0）时进行。第二次是（j=1，i=0）。所以，让我们填充一个网格，其中每个位置的值是每个单元格的计数次数。会是这样的：
你现在可以看到这幅画了。将这个网格中的所有内容相加，就可以知道最内部的循环执行了多少次。
第一行有1 n
第二行有2个（n-1）
第三行有3个（n-2）
您可以看到（n-j）*（j+1）的模式是每行的总和。
对行求和得到总数。
你得到的结果如下：
这只是最内部循环执行的次数。现在，最内部的循环没有被执行。这部分要容易得多。它只是网格中非彩色方块的数量。
因为这是一个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
内环执行数：167000
执行总数：167666500
n=10000个
内部循环执行：16670000
执行总数：1667665 000
n=10万
内环执行数：166671666700000
执行总数：1666765万
n=100000000（仅仅是为了lolz，你已经可以看到模式了）
内环执行数：16666700000000
执行总数：166650000000
最后我要说的是，既然你们已经读到了，这是一个o（n3）函数。
我不会过多地讨论它，但是最内部for循环执行次数的总和简化为
将计算最内部循环未执行次数的两个术语相加，将相似的术语分组以便于简化，最终结果如下：
您可以使用最后两个公式来验证我在上面共享的数据。您还可以通过向循环中添加计数器并运行它们来进行经验验证，以查看它们执行的次数，并将其与这些公式给出的值进行比较（对于像我提供的值一样大的值，您需要使用它们）
BigInteger或其他任意大的数字格式）。如果你不信任我，或者你的电脑，你也可以试着把这些信息扔到一个在线工具上，比如wolfram alpha。最后，如果这是一道考题，你可以把它拿给你的教授，展示这个问题的性质和准确的人数for-loop执行死刑n是数组的长度A. 如果这一切都是错误的，我至少已经证明了10次方幂是正确的。希望这能有所帮助。pokxtpni2#
更新：根据@loganrussell48的分析和下面的评论，我得出的结论
n^2这是错误的。错误答案：
更大的因素，如
n^2“日 eclipse ”较小的因素，比如你正在搜索的因素（我们知道它比n，这就是为什么答案会小于n^3).可以肯定地说你的大o比
n^2但小于n^3. 如果你查阅一份时间复杂性列表（比如https://en.wikipedia.org/wiki/time_complexity#table_of_common_time_complexities)你会发现这两种复杂性是相邻的。大o就是简单化。常数因子退出。较小的因素退出。在这种情况下，第三个因素
n(n * n * n)比…小得多n. 条件在一半时间内满足，并在两个时间间隔内执行i以及j次数（均小于n，因此使用估计值（n的一半）。第三个因素n现在比现在小得多n.一般复杂性小于
n与…相比是微不足道的n^2.在这种情况下，
n^2是你想要传达的重要信息。