算法复杂度(渐近)

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) a = j * j -2 * j + 3)，其中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++)

要么执行一次- when 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)