如何做復發關係？

NSO我們被教導約遞推關係在一天前，我們給予一些代碼與實踐：如何做復發關係？

int pow(int base, int n){ 

if (n == 0) 

    return 1; 

else if (n == 1) 

    return base; 

else if(n%2 == 0) 

    return pow(base*base, n/2); 

else 

return base * pow(base*base, n/2); 

}

我必須得到它的封閉形式的最遠的是T（N）= T（N/2^k）+ 7k。我不知道如何去任何進一步的作爲給我們的例子很簡單，不利於那麼多。你如何真正解決這個代碼的遞歸關係？

來源

2014-01-29 user3249400

從何從7？什麼是k？ T應該表示算法的複雜性嗎？ – amit

7是我從的方式，是的，T表示算法的複雜度獲得碼，K =日誌n的操作計數了。 – user3249400

讓我們只計算pow的呼叫中的乘數，表示爲M(N)，假設它們支配成本（現在是強烈無效的假設）。

通過我們看到的代碼的檢查的是：

M(0) = 0（沒有乘法爲N = 0）

M(1) = 0（沒有乘法爲N = 1）

M(N)，N> 1，N即使是= M(N/2) + 1（對於偶數N，在一次乘法後遞歸調用）

M(N)，N> 1，N odd = M(N/2) + 2（對於奇數N，一次乘法後的遞歸調用，fol降低了一倍）。

這復發受了一點，它以不同方式處理偶數和奇數的事實複雜化。我們只會考慮偶數或奇數序列來解決這個問題。

讓我們首先處理N是2的冪的情況。如果我們迭代公式，我們得到M(N) = M(N/2) + 1 = M(N/4) + 2 = M(N/8) + 3 = M(N/16) + 4。我們很容易地發現模式M(N) = M(N/2^k) + k，使溶液M(2^n) = n如下。我們可以把它寫成M(N) = Lg(N)（以2爲底的對數）。我們有M(2^n-1) = M(2^(n-1)-1) + 2 = M(2^(n-2)-1) + 4... = 2(n-1)。或M(N) = 2 Lg(N+1) - 2。

一般N的確切解決方案可以相當涉及，但我們可以看到Lg(N) <= M(N) <= 2 Lg(N+1) - 2。因此M(N)是O(Log(N))。

來源

2014-01-29 16:22:56

如何做復發關係？

回答

相關問題