2

我不是 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 个单独的总变量，不变量会更容易定义吗？

谢谢你提供的所有帮助。

这个函数的增长顺序也是：Θ（n ^ 3）？

4

2 回答 2

2

当面对这样一个增量计算总和的循环时，要寻找的一个很好的不变量是到目前为止您计算的总和是否等于您认为的总和的第一部分。在这种情况下，您想要计算前 n 个正完美立方体的总和，并通过一次添加一个立方体来实现。因此，一个可能的不变量是

tot = sum (j 从 0 到 i) j 3

另外，i和n之间的关系是什么？好吧，我们可能应该有 i ≤ n + 1。为什么是 n + 1？这是因为在最后一次迭代中，当 i = n 时，我们仍然会增加 i。使用这两个不变量，您可以证明此循环计算了正确的值。

至于运行时，您可以很容易地计算出来。首先，每次迭代完成了多少工作？奥（1）？上）？O(n 2 )? 那么，有多少次循环迭代呢？奥（1）？上）？O(n 2 )? 这两个术语的乘积会给你答案。

希望这可以帮助！

于 2012-02-08T03:43:59.217 回答
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;

然后，您可以将其翻译成 Sigma 表示法：

在此处输入图像描述

于 2014-04-15T14:31:24.533 回答