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)