Пример свойства алгоритмов "разделяй и властвуй"

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

Постоянный член 1 должен быть равен 2, поскольку функция выполняет один рекурсивный вызов для каждого из двух фрагментов, на которые она делит задачу. Правильная граница - 2N-1, а не N. Надеемся, эта ошибка будет исправлена ​​в следующей редакции вашего учебника или, по крайней мере, в ошибках.