ネストされたforループのプリミティブ操作

Question

プリミティブ操作の総数の計算方法がわかりません。 私は自分でこれをしましたが、これは正しくありません。このコードの

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） 。

Answer 1

内側から計算する必要があります。 内側のforループを1回実行すると、（i-j + 1）のプリミティブ加算演算が実行されます。しかし、これは、（i-1 + 1）+（i-2 + 1）+ ..（i-i + 1）= i *（i + 1）のカウントにつながる、/2プリミティブ演算。今度は、（1/2）*（1 * 1 + 2 * 2 + .. + n * n）+（1/2）（1+ 2 + .. + n）=（1/2）（n * 1）（2n + 1）/ 6 + n（n + 1）/ 2）=（1/12）* 2 * n^3 + 6 * n^2 + 4 * n）= O（n^3）プリミティブ演算。最終的なカウントは、nの関数でしかなく、他の変数はありません。