algorithm - 算法复杂度（渐近）

Question

有人可以确认我这个算法的复杂度是 O(n^2) 吗？

a = 0
b = 0
c = n
while (b <= c)
{
    for (j = b; j<=c; j++)
    {
        a = j * j -2 * j + 3
    }
    b = b + 3
    c = c + 2
}

Answer 1

内循环执行c - b + 1次数。内部循环体的每次执行都a = j * j -2 * j + 3需要恒定（有界）时间（假设我们正在处理固定宽度的整数类型，否则它将取决于使用的乘法算法[和加法，但这很难以乘法的方式实现更快]），所以外循环体的执行是O(d)（Θ(d)偶数），其中d = c - b + 1.

控制外循环的变量的更新

b = b + 3
c = c + 2

c - b每次执行外循环主体时将差值减少 1，因此外循环执行n+1次数，并且您总共有O(n²)，因为

 n                   n+1
 ∑ (n+2k - (3k) +1) = ∑ j = (n+1)(n+2)/2
k=0                  j=1

它甚至是Θ(n²)，除非编译器直接优化并将所有变量设置为其最终值。

---

用错字回答原始问题：

内循环

for (j = b; j==c; j++)

将执行一次b == c或根本不执行，因此外部循环的主体是O(1). 外循环中的更新

b = b + 3
c = c + 2

表示c-b每次执行循环体时差值减1，所以

b = 0
c = n
while (b <= c)

将执行n+1时间 - 总计：O(n)。

Answer 2

b = b + 3
c = c + 2

使得 b 在外循环的每次迭代中都赶上 c 一个。这意味着外部循环运行 n+1 = O(n) 次，因为它们最初彼此相距 n 次。

内部循环执行 (c - b + 1) 次。我们知道它们最初相距 n，并且在外循环的每次迭代中接近 1。

查看内部循环运行的次数，它看起来像： (n, n-1, n-2, ..., 1) 总共

1 + 2 + ... + n = (n)(n+1)/2  = O(n^2)

Answer 3

每次你的外循环

while(b <= c)

执行时，b 和 c 比以前更接近 1。但是， b 和 c 从相距 n 的距离开始，因此您的内部 for 循环首先执行 n+1 次，然后执行 n 次，然后执行 n-1 次，依此类推，直到最终执行 1 次然后你的程序完成。因此，您的运行时间与

(n+1) + n + (n-1) + (n-2) + ... + 1

你可以查看递增整数公式的总和，看看这个总和等于

(n+2)(n+1)/2 = O(n^2)

所以你的运行时间是 O(n^2)