嵌套的for循环运行时间的问题

我一直在考虑这个问题几天，现在挂上了计算第二个嵌套for循环运行的次数。我相信我有确定其他两个for-loop的运行时间的正确公式，但是第三个我挂了。我有第一个循环运行n-1次。确定循环＃2运行次数的公式是：总数1到n-1。如果有人能够帮助我理解如何找到循环＃3运行的次数，那么将不胜感激。嵌套的for循环运行时间的问题

for (int i=1; i<=n-1; i++) { 
     for (int j=i+1; j<=n; j++) { 
      for (int k=1; k<=j; k++) { 
      } 
     } 
    }

来源

2011-09-10 John

为什么你不试一试呢？将'x ++'添加到循环的内部，并尝试使用各种'n'。另外，这个问题被标记为[tag：big-o]，为什么？计算确切数量与Big-O无关。 – svick

这就是我在我的小程序中所拥有的。我遗漏了几行代码以使代码更具可读性。添加x ++会告诉我循环将运行多少次，但我正在寻找一个使用n的数学表达式，它会给我答案。 – John

第三循环运行C倍：

C = Sum(Sum (Sum (1 , k = 1 .. j) , j = i+1 .. n) , i = 1 .. n-1) 
    = Sum(Sum (   j   , j = i+1 .. n) , i = 1 .. n-1) 
    = 2 + 3 + 4 + ... + n 
     + 3 + 4 + ... + n 
    ... 
        + n 
    = 2*1 + 3*2 + 4*3 + 5*4 + ... + n*(n-1) 
    = (1*1 + 1) + (2*2 + 2) + (3*3 + 3) + ... + ((n-1)*(n-1) + n-1) 
    = (1^2 + 2^2 + ... (n-1)^2) + (1 + 2 + 3 + ... + (n-1)) 
    = (n-1)*n*(2*n-1)/6 + (n-1)*n/2 
    = (n-1)*n*(2*n+2)/6 
    = O(n^3)

在这里，我使用的公式：

1^2 + 2^2 + ... + m^2 = m*(m+1)*(2*m+1)/6

和

1 + 2 + ... + m = m*(m+1)/2

来源

2011-09-10 23:32:02

谢谢彼得！这是一个很大的帮助。 – John

嵌套的for循环运行时间的问题

回答

相关问题