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，但我不完全确定如何将它们定义为循环不变量。

如果我在每个 while 循环体中都有 3 个单独的总变量，这些变量在第一个循环中 i++ 之前添加到主总数中，那么不变量会更容易定义吗？

谢谢你提供的所有帮助。

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

（如果您计算的金额是正确的）。