你會如何去發現這個算法的複雜性？

Question

function alg1(n) 
1 a=0 
2 for o=1 to n do 
3  for t=1 to o do 
4   for k=t to o+t do 
5   a=a+1 
6 return(a) 

如果有人能指導我如何找到最糟糕的情況，以及如何獲得alg1的輸出作爲n的函數，我將非常感激。謝謝！從最後的循環

Answer 1

減牛逼，使之成爲

for k=0 to o do 

現在2個內最環路將辦理O運行（O^2）時間爲鄰的每個值。答案是

1^2 + 2^2 + ... n^2 

其等於

N（N + 1）（2N + 1）/ 6。因此，它的順序爲O（n^3）

Answer 2

我們可以計算這個代碼執行的增量的確切數目。首先，讓我們來取代

for k=t to o+t do 

與

for k=1 to o+1 do 

這一變化後，兩個內環看起來像這樣

for t=1 to o do 
    for k=1 to o+1 do 

這些循環的迭代次數顯然是o*(o+1)。迭代的總數可以通過以下方式計算：

我們可以用大O符號時排除係數多項式的低階方面。因此，其複雜性爲O（n^3）。