キューブアルゴリズムの総和に対するループ不変量は何ですか？

Question

私は三重累乗の不変量が何であるか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にしますが、ループ不変量としてそれらを定義する方法は完全にはわかりません。

最初のループでi ++の前にメインの合計に追加されたwhileループの各ボディに3つの別々の合計変数があると、インバリアントを定義しやすくなりますか？

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

Answer 1

は、私はあなたが以下のようにそれらを定義することができると思う：

LI1 <= (i^2(i+1)^2)/4 
LI2 <= (i+1)^3 + (i^2(i+1)^2)/4 
LI3 <= (i+1)^2 + i^3 + (i^2(i+1)^2)/4 

（あなたの計算量が右である場合）。