c++ - 数据结构-运行时间

只是一个混乱...
C ++示例代码的一部分如下



我只是重新编辑整个帖子。抱歉造成任何混乱

int i, j;
i = 0;    // c1
j = 0;    // c2
while (i < n)   // (n+1)c3
{
  i++;   // n c4
   while ( j < i)  // (2+3+....+n+(n+1)c5
   {
     j++;   // (1+2+...+n)c6
   }
  j = 0;  // c7
}

显然，c1，c2和c7是恒定的。我们对这些内容不感兴趣，它们对确定运行时间并不重要。

我不了解的是c5和c6。

为什么c5是2 + 3 + 4 ... + n +（n + 1）？为什么以2开头，而不是1 + 2 + 3 ... +（n + 1）？？？
注意我们可以重写C5->（n *（n-1）/ 2）+ n

对于c6，此组合可以重写为n *（n-1）/ 2

最初我以为C6为n，因为C6取决于两个条件，第一个while和第二个while循环。但是由于j总是回到0，所以我们实际上取决于第一个while循环。由于n

  n = 3
  
  0   
  1   
  2   
  3

有人可以明确说明如何确定C5和C6吗？
很抱歉，这个问题对专家们来说很愚蠢
谢谢！

最佳答案

在这里，您的运行时间为2n。每次i递增时，j就会小一，因此内部循环只执行一次。

i=0, j=0 // init
i=1, j=0 // outer loop
i=1, j=1 // inner loop
i=2, j=1 // outer loop
i=2, j=2 // inner loop

通常，您可以在外部循环中将j重置为0。在这种情况下，您的运行时为n*(n-1)/2