分而治之算法的属性示例

Question

我在理解划分算法的以下属性方面遇到困难。

将大小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。我想念什么？

Answer 1

您不会缺少任何东西。定理及其证明是错误的。错误在这里：

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

恒定项应为2，因为该函数对其将问题划分为两个部分中的每一部分都进行了一个递归调用。正确的界限是2N-1，而不是N。希望此错误将在您的下一版本的教科书中或至少在Errata中解决。