分而治之算法中的時間複雜度

讓我們來看看這個例子。 http://www.geeksforgeeks.org/archives/4583方法2：它給了T（n）= 3/2n -2，我不明白爲什麼？

對不起，如果我給了你一個額外的頁面打開，但我真的很想理解一個很好的高層次，這樣我就可以自己找到這些算法的複雜性，你的回答是非常感謝。

2011-12-21 Aj Gauravdeep

那麼解釋一下，我們實際上需要知道你目前的理解水平。例如，您一般對遞歸算法和複雜性分析的實力。我建議你嘗試查找一些互動幻燈片。 – 2011-12-21 08:45:38

由於某種原因無法打開此鏈接。我仍然會試一試。當您使用分治策略時，您所做的是將問題分解爲許多較小的問題，然後將小問題的解決方案結合起來以獲得主要問題的解決方案。如何解決較小的問題：通過進一步分解。這個分解過程一直持續到您達到問題小到可以直接處理的程度。

如何計算時間複雜度：假設您的算法花費的時間是T（n）。注意，所花費的時間是問題大小即n的函數。

現在，注意你在做什麼。你把問題分解成k個部分，每個部分的大小爲n/k（它們的大小可能不相同，在這種情況下，你必須單獨添加它們所花費的時間）。現在，你會解決這些k部分。每個部分所花費的時間將是T（n/k），因爲問題的大小現在減小到n/k。你正在解決這些問題。所以，它需要k * T（n/k）時間。

解決了這些小問題之後，您將結合他們的解決方案。這也需要一些時間。那個時間將再次成爲問題規模的函數。（它也可以是恆定的）。假設那時候是O（f（n））。

因此，通過你的算法採取的總時間爲： T（N）=（K * T（N/K））+ O（F（N））

你已經有了一個遞推關係現在你可以解決得到T（n）。

來源

2011-12-21 08:51:39 Divya

隨時要求澄清。 – Divya 2011-12-21 08:53:13

謝謝Divya。雅，我去了那個網站，看起來已經達到了它的容量，因此無法提供服務。其實你解釋我已經知道，直到那一部分，但是，它的數學令我困惑。但是，我的老大學書籍，並試圖瞭解。非常感謝您的時間。 – 2011-12-22 03:11:09

如果你正在尋找「如何解決復發關係」，你可能想要檢查這個鏈接http://www.cs.ucr.edu/~jiang/cs141/recur-tut.txt這是一個快速教程涵蓋解決復發關係的各種方法。樂於幫助！ :) @Leoheart – Divya 2011-12-22 03:47:32

作爲該鏈接表示：

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 
    T(2) = 1 
    T(1) = 0

爲T(2)，它與返回之前比較單一的位置。對於T(1)這是一個沒有任何比較的基礎。
對於T(n)：你遞歸調用該方法對數組的兩半，比較兩個（最小值，最大值）元組找到真正的最小值和最大值，它給你上面T(n)式

If n is a power of 2, then we can write T(n) as: 

    T(n) = 2T(n/2) + 2

這很好地解釋自己。

T(n) = 3/2n -2

在這裏，你感應解決它：
基本情況：對於n = 2：T(2) = 1 = (3/2)*2 -2
我們假設T(k) = (3/2)k - 2每個k < n
T(n) = 2T(n/2) + 2 = (*) 2*((3/2*(n/2)) -2) + 2 = 3*(n/2) -4 + 2 = (3/2)*n -2
（*）誘導的假設，是真實的，因爲

因爲我們證明感應是正確的，所以我們可以得出結論：T(n) = (3/2)n - 2

來源

2011-12-21 09:01:58 amit

嗨，我們如何用k + 1項來證明這個證明？ – RichArt 2017-08-13 01:41:26

分而治之算法中的時間複雜度

回答

相關問題