嵌套for循环的基本操作

我很困惑如何计算原始操作的总数。我是通过我自己做到的，但这是不正确的。嵌套for循环的基本操作

for (i: 1 to n) --------- n 
    for (j: 1 to i) -------- n (i - 1) 
     for (k: j to i) ---------------- n (n - 1) * (i - 1) 
      s= s + 1 ------------- n (n - 1) * (i)

总此代码原始操作数是N + N（I - 1）+ N（N-1）*（I-1）×N（N-1）*（I） 。

来源

2017-01-28 suleman

https://www.wolframalpha.com/input/?i=sum(sum(i-j%2B1+for+j+%3D+1..i)+for+i+%3D+1..n） –

您应该从内向外进行计算：对最内层循环执行单次执行（i-j + 1）基元相加操作。（i-1 + 1）+（i-2 + 1）+ .. +（i-i + 1）= i *（i + 1）的计数，/2原始操作。现在来到最外面的for循环，它重复所有的操作n次，总计数为（1/2）*（1 * 1 + 2 * 2 + .. + n * n）+（1/2）（1+ （n + 1）/ 2）=（1/12）*（2 + ... + n）=（1/2）（n *（n + 1）（2n + 1）/ 6 + n * n^3 + 6 * n^2 + 4 * n）= O（n^3）原语操作。最终计数应该只是n的函数，而不是其他变量。

来源

2017-01-28 22:51:40

嵌套for循环的基本操作

回答

相关问题