算法的複雜性（漸近）

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 

由1中的外環的身體的每個執行減小差c - b的更新，因此，外循環被執行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 

使得它通過外部循環的每次迭代一次追上c。這意味着外部循環運行n + 1 = O（n）次，因爲它們最初彼此是n。

內循環執行（c-b + 1）次。我們知道它們最初是分開的，並且在外部循環的每次迭代中靠近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，所以你的內循環首先執行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）