T（n）=Θ格式的計算複雜性

Question

有人可以解釋一下這段代碼（以及爲什麼）的大theta格式的複雜性嗎？這是我從這個話題的第一個任務，我有點困惑。任何形式的幫助將不勝感激！

for i <-- 1 to n-1 
    do j <-- 1 
    while j <= 2*(i+1) 
     do j <-- j + 1 

Answer 1

我可能是錯與±1，但我認爲的將要執行的步驟的數目是：

sum_ {I = 1}^{N - 1} 2 *（ⅰ +1）= 2sum_ {i = 1}^{n-1} + 2（n-1）=（n^2-n）+（2n-1）= n^2 + n + 1

Answer 2

n^2因爲你有一個循環循環，所以這意味着你的指令執行n * n次

Answer 3

首先你的僞代碼根據慣例不完全正確。

for i <-- 1 to n-1 
    do j <-- 1 
    while j <= 2*(i+1) 
     do j <-- j + 1 

上述僞代碼應該更清楚，如果表示爲如下，

for i = 1 to n-1 
    for j = 1 to (2*(i+1)) 
     // Body of the inner loop 

上述僞代碼的複雜性只有在內部循環的主體包含恆定時間表達式來分析。例如，如果操作數足夠小，加法或減法就是一個常量時間操作。另一方面，如果循環包含對另一個函數的調用，那麼複雜度也取決於這個被調用函數的複雜度。

如果循環的主體只包含常量時間表達式，那麼複雜度可以分析如下。

外循環執行n-1次。 內循環執行2*(i+1)次。

因此，內循環內的語句執行4,6,8，...，最後2n次。所以執行的指令總數，

4 + 6 + 8 + ... + 2n 
= 2 (2 + 3 + 4 + ... + n) 
= 2 (n(n+1)/2 - 1) 
= n(n+1) - 2 

那裏執行的指令總數，ñ - N - 2。

因此複雜度爲Θ（n ）。