algorithm - 如何计算程序的最坏情况(Big O)

Question

请原谅故意冗长

这是一个小程序摘录:

for i=1 to n
  j= 0;
  while(j<=n);
  j=j+1;

如果我必须找到这段代码的复杂性(大 O):

我将首先计算内部循环将执行多少次，在本例中为 n+1 次，因为从 1 到 n，它是 n 次，并且由于 j 为 0，它添加到 while 循环中。所以 while 循环总共 n+1 次。

外层for循环执行的次数为n次，因为从1到n，总次数为n。因此总和是n+1+n是2n+1。

丢弃所有常量是一个很大的 O(n)。

是否正确？我找到这个例子的网页说外循环将运行 n(n+1)/2 次。我不明白这一点。请帮忙!

Answer 1

没有。对于 i 获取的每个值(其中有 n)，您运行 while(内部)循环 n+1 次 (j=0,j=1,...j=n)。

因此，j=j+1行被执行的总次数是n*(n+1)，在O (n^2)