algorithm - 分而治之算法的属性示例

Question

我无法理解分而治之算法的以下属性。

A recursive method that divides a problem of size N into two independent (nonempty) parts that it solves recursively calls itself less than N times.

证明是

A recursive function that divides a problem of size N into two independent (nonempty) parts that it solves recursively calls itself less than N times. If the parts are one of size k and one of size N-k, then the total number of recursive calls that we use is T(n) = T(k) + T(n-k) + 1, for N>=1 with T(1) = 0. The solution T(N) = N-1 is immediate by induction. If the sizes sum to a value less than N, the proof that the number of calls is less than N-1 follows from same inductive argument.

我完全理解上面的形式证明。我不明白的是这个属性如何与通常用于演示分而治之思想的示例相关联，尤其是与寻找最大问题相关的示例:

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; 
  } 

在这种情况下，当 a 由 N=2 个元素组成时，max(0,1) 会再调用自己 2 次，即 max(0, 0) 和 max(1,1)，等于 N。如果N=4，max(0,3)会调用自己2次，然后后面的每次调用也会调用max 2次，所以调用是 6 > N。我错过了什么？

Answer 1

您没有遗漏任何东西。定理及其证明是错误的。错误在这里:

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

1 的常数项应该是 2，因为该函数对将问题分成的两部分中的每一部分进行一次递归调用。正确的边界是 2N-1，而不是 N。希望这个错误将在您的教科书的下一版中得到修复，或者至少在勘误表中得到修复。