在程序中尋找循環不變量來計算立方體的總和？

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 2 + 1）^）/ 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個正完美立方體的總和，並通過逐個添加立方體來實現。因此一種可能不變將是

TOT =總和（j從0至i）.J

此外，什麼是i和n之間的關係是什麼？那麼，我們可能應該有這個我≤ n + 1.爲什麼n + 1？這是因爲在最後一次迭代中，當我= n時，我們仍然會增加i。使用這兩個不變式，你可以證明這個循環計算出正確的值。

至於運行時，你可以很容易地計算出來。首先，每次迭代需要完成多少工作？ O（1）？上）？ O（n ）？那麼，有多少次循環迭代？ O（1）？上）？ O（n ）？這兩個術語的結果會給你你的答案。

希望這會有所幫助！