プログラムでループ不変量を見つけると、キューブの合計を計算できますか？

Question

私は3倍のパワーの合計で不変量が何であるか100％確信していません。

注：nは常に負ではない値です。

擬似コード：

triplePower(n) 
    i=0 
    tot=0 
    while i <= n LI1 
     j = 0 
     while j < i LI2 
      k = 0 
      while k < i LI3 
       tot = tot + i 
       k++ 
      j++ 
     i++ 

私はその乱雑を知っていて、はるかに簡単な方法で行うことができるが、これは私は（主にアルゴリズム分析の練習のために）行うことを期待していますものです。

私は3つのループ不変量を思いつきます。 LI1、LI2、およびLI3。
私はLI1の不変量は、tot =（i^2（i + 1）^ 2）/ 4（0からiまでの合計の方程式）と関係があると考えています
私は、 LI2やLI3のために何をすべきかを知っている。 LI2のループはi^3を作り、LI3はi^2にしますが、ループ不変量としてそれらを定義する方法は完全にはわかりません。

whileループの各ボディに3つの別々の合計変数があると、不変量を定義しやすくなりますか？

ご協力いただきありがとうございます。

この関数の次数もまたです：Θ（n^3）？

Answer 1

あなたのアルゴリズムは、この（私はあなたがC言語の構文に慣れている願っています）のように簡略化することができます。

tot = 0; 
for (i = 0 ; i <= n ; i ++) 
    for (j = 0 ; j < i ; j ++) 
     for (k = 0 ; k < i ; k ++) 
      tot = tot + i; 

そして、あなたはシグマ表記に翻訳することができます

Answer 2

このようなループでは、累積加算を徐々に計算すると、今までに計算した総和が、考えている合計の最初の部分と等しいかどうかがわかります。この場合、最初のn個の正の完璧な立方体の合計を計算し、一度に1つずつ立方体で加算します。このように一つの可能​​な不変の

TOT = SUM（jはiを0からなる）

さらにJということでしょう、私とnとの関係は何ですか？さて、私はおそらくそれを持っている必要があります。≤ n + 1なぜn + 1？これは、最後の反復では、i = nのときでも、私はとにかくiをインクリメントするからです。これらの2つの不変量を使って、このループが正しい値を計算することを証明できます。

ランタイムに関しては、これを非常に簡単に計算できます。まず、各反復でどれくらいの作業が行われていますか？ O（1）？に）？ O（n ）？次に、ループの繰り返し回数はいくつですか？ O（1）？に）？ O（n ）？これらの2つの用語の積によって、あなたの答えが得られます。

希望すると便利です。