计算循环运行的次数（大 O）

Question

我得到了这样的伪代码语句：

function testFunc(B)
  for j=1 to B.length-1
     for i=1 to B.length-j
       if(B[i-1] > B[i]
         swap B[i-1] and B[i]

我被告知要在 Big o O(n^2) time.

中证明此算法运行s

所以我知道第一个for循环运行s n次，因为我相信它是包容性的。我不确定其余的行，第二个 for 循环运行 n-2 次吗？任何帮助将不胜感激。

Answer 1

内循环运行次数减少。看一个具体的例子。如果B.length为10，那么内循环的内容会执行10次，然后9次，以此类推，直到1次。

使用高斯方程：

n(n+1) / 2

你可以看到在该示例中，内部代码将执行 55 次。 (10(10 + 1)/2 = 55)

因此，对于 n 次，它将运行 n(n + 1) / 2 次。这相当于：

1/2 n^2 + 1/2 n

对于Big-Oh，n的系数和较小的值被忽略，所以这相当于O(n^2)。

Answer 2

如果N = B.length，则外循环运行N-1次，内循环运行(N-1)+...+3+2+1次，共(N-1) * (N/2) = N^2/2 - N/2次，即O(n^2).

Answer 3

假设 B.length 是 5 次。因此，外循环将运行 4 次。在外循环的第一次迭代中，内循环将运行 4 次；在第二次迭代中，内部循环将运行 3 次；第三次迭代2次；第四次是 1 次。

让我们以几何方式展示结果：

AAAA
AAA
AA
A

每个A代表到达嵌套循环内的conditional/swap，你想知道，一般来说，有多少个A。计算它们的一种简单方法是将三角形加倍以生成矩形：

AAAAB
AAABB
AABBB
ABBBB

你可以很快看到边长为 N 的三角形，有 N*(N-1)/2 个 A，因为它们是 N*(N-1) 个由 A 组成的矩形的一半。执行乘法并忽略 1/2 的比例因子（因为大 O 不关心常数），我们看到有 O(N^2) 个 A。

Count amount of times loop runs (Big O)