遞歸算法的時間複雜度（僞代碼）

-5

如果我們有這樣的代碼（僞）這個遞歸調用的時間複雜度是多少？假設以下沒有說明的東西被認爲是恆定時間。遞歸算法的時間複雜度（僞代碼）

a,b,c > 0 

//some code above, then we get here 

for i = 0 to a 
    recursive(i,b) 

//code continues 

FUNCTION recursive(i,b) 
if b = 0 
    return 0 

for j = i+c to a 
    recursive(j,b-1) 
ENDFUNC

編輯我主要是我有麻煩確定它是否是指數與否。深度顯然是b，並且在遞歸函數中調用了O（b * a），但是主循環也調用了它，使得我認爲它應該總是：O（a^2 * b），但我不太明白指數複雜度是如何產生的，所以我想知道它是否可以代替？

來源

2017-10-04 tiggybits

你在哪裏分析自己的複雜性問題？您需要計算每個函數被調用的頻率。這產生一個依賴於使用變量的數字，比如'a + 2b + c^a'或類似的東西。之後，派生一個複雜類很容易。 – Zabuza

@ikegami應該寫成b - 1. – tiggybits

假設b在遞歸函數中是局部的，所以b-1不會影響主循環中的b – tiggybits

首先，讓我們來看看兩個簡單的嵌套循環第一：

for i (1..N) { 
    for j (1..N) { 
     f(); 
    } 
} 

for i (1..N) { 
    for j (i..N) { 
     g(); 
    } 
}

f()被稱爲N*N = N² = O(N²)倍。

g()稱爲N+(N-1)+...+5+4+3+2+1 = N(N+1)/2 = N²/2 + N/2 = O(N²)次。

正如你所看到的，內循環的起始位置並不重要，複雜性將是相同的。

其次，讓我們看看如果添加一層嵌套，會發生什麼。

for i (1..N) { 
    for j (1..N) { 
     for k (1..N) { 
      h(); 
     } 
    } 
}

我們已經知道這兩個外環路O(N²)，和我們正在做的N倍，所以我們得到O(N³)。我們可以看到指數是嵌套量。

如果我們開始展開recursive，我們得到

for i2 = i+c to a 
    recursive(i2, b-1)

這是

for i2 = i+c to a 
    for i3 = i2+c to a 
     recursive(i3, b-2)

這是

for i2 = i+c to a 
    for i3 = i2+c to a 
     for i4 = i3+c to a 
      recursive(i4, b-3)

等

正如你所看到的，你有b嵌套循環遍歷一個子集a-c元素。應用我們上面學到的，recursive需要O((a-c)^b)時間。

整個代碼（即調用recursive加上外部循環）會添加另一個圖層，因此需要O((a-c)^b * a)時間。

來源

2017-10-04 18:50:57 ikegami

遞歸算法的時間複雜度（僞代碼）

回答

相關問題