下面我试图显示算法执行的加法数的下限请告诉我我的分析是否正确。
这是一个计算n个元素的数组a的所有i，j i
for i=1 to n
for j = i+1 to n
B[i,j] = 0
for i < j:
B[i,j] += A[i,j]
return B
我认为这个算法至少需要N^3个操作。
我的论点是：
来自外部forloop的n次迭代
如果i=n\2，那么内部forloop将至少迭代n/2次
如果i=n/2和j=n，则从i到j的元素总和至少需要n/2个加法
因此，该算法执行n*n/2*n/2=（n^3）/4个操作。
最佳答案
很接近，但你的证据并不能完全证明你想要什么。你说：
来自外部forloop的n次迭代
好吧，那么至少Ω（n）
如果i=n\2，那么内部forloop将至少迭代n/2次
当然，但是i=n/2只适用于一个迭代，所以这证明总共只有n/2个迭代再次至少Ω（N）
如果i=n/2和j=n，则从i到j的元素总和至少需要n/2个加法
是的，但是这些条件只发生一次，所以这只能再次证明Ω（n）。
你要的证据是这样的：
当i在每一次迭代中，n-i>=n/2，并且内环为那么多迭代运行，因此至少有（n/2）（n/2-1）个内环迭代。
至少有一半的内环迭代——特别是至少（n/4）（n/2-1）-1——对至少n/4个元素求和，因此需要n/4-1个元素的加法。
所以至少有（（n/4）（n/2-1）-1）（n/4-1）个加法，单位是Ω（n^3）
关于algorithm - 如何证明嵌套forloop的操作数下限，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48434371/