algorithm - 立方求和算法的循环不变量是什么？

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++

我知道这很麻烦，可以用更简单的方式完成，但这是我应该做的(主要用于算法分析练习)。

我要提出三个循环不变量； 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

(如果您计算的金额正确)。