分而治之算法的屬性示例

我在理解分而治之算法的以下屬性時遇到了問題。分而治之算法的屬性示例

劃分大小N的問題分解成兩個獨立的（非空），該解決了遞歸調用自身小於N倍份的遞歸方法。

證明是

遞歸函數劃分大小N的問題分解成兩個獨立的（非空），該解決了遞歸調用自身小於N倍份。如果這些部件是尺寸爲k和尺寸爲N-k中的一個，則我們使用的遞歸調用總數爲T(n) = T(k) + T(n-k) + 1，對於N>=1和T(1) = 0的總數爲。解決方案T(N) = N-1立即通過歸納。如果尺寸總和爲小於N的值，則證明呼叫數小於N-1的證明來自於相同的歸納論證。

我完全理解上面的形式化證明。我不明白的是這個屬性是如何連接到通常用於演示的分而治之的想法的例子，特別是對發現的最大問題：

static double max(double a[], int l, int r) 
    { 
    if (l == r) return a[l]; 
    int m = (l+r)/2; 
    double u = max(a, l, m); 
    double v = max(a, m+1, r); 
    if (u > v) return u; else return v; 
    }

在這種情況下，當一個由N=2元素max(0,1)將自稱2次以上，即max(0,0)和max(1,1)，相當於N。如果N=4，max(0,3)將自己調用2次，然後每個後續調用也會調用最多2次，所以總的調用次數爲6 > N。我錯過了什麼？

來源

2014-01-30 Artyom Dmitriev

你不會錯過任何東西。該定理及其證明是錯誤的。該錯誤是在這裏：

T(n) = T(k) + T(n-k) + 1

1的常數項應該是2，作爲功能使得一個遞歸調用用於每個兩件到其中將所述的問題。正確的界限是2N-1，而不是N.希望這個錯誤會在你的教科書的下一版本中修復，或者至少在勘誤表中。

來源

2014-01-30 14:31:40 user2357112

現在我安心 - ）。我實際上在Robert Sedwick的Java算法中找到了。他的C++書有相同的[錯誤]（http://stackoverflow.com/questions/12264936/number-of-recursive-calls-in-recursive-function-analysis）。 –

分而治之算法的屬性示例

回答

相關問題