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) even), 其中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)。