Я читаю метод дерева рекурсии во Введении в Алгоритм, и когда я попытался применить его, я обнаружил некоторую несогласованность, как показано ниже:
Чтобы вычислить T(n) = 3T(n/4) + c*n^2, книга предлагает решение: Рисунок из книги Изображение из книги . В моем понимании, мы должны сначала рассчитать стоимость на каждом уровне, за исключением нижнего уровня, где мы имеем T (1) = Θ (1). Затем мы добавляем T1 * (количество листовых узлов) к предыдущей сумме, чтобы получить окончательный результат.
Однако, когда я пытаюсь применить эту технику к другому упражнению, возникает вопрос в книге, возникает проблема.
Чтобы вычислить верхнюю границу для T(n) = T(n/2) + T(n/4) + T(n/8), после построения дерева рекурсии мы видим, что затраты на уровне i имеют стоимость (7/8)^i * n, и для получения окончательного ответа мы делаем (n +(7/8)*n + (7/8)^2 * n + (7/8)^3 * n + ... + (7/8)^( (log2(n)-1 )) ) + Θ( 3^(log2(n) ) = Θ( n^(log2(3) ) (я вычисляю лог на основе 2, потому что мы рассчитываем верхнюю границу).
Однако решение здесь http://sites.math.rutgers.edu/~ajl213/CLRS/Ch4.pdf использует другой подход. А именно, он не обрабатывает нижний уровень, отличный от других уровней, и просто вычисляет (7/8)^i * n, и чтобы получить окончательный ответ, мы делаем (n +(7/8)*n + (7/8)^2 * n + (7/8)^3 * n + ... + (7/8)^(log2(n) ) ) = Θ( n ).
Таким образом, вопрос, одним словом, заключается в несоответствии двух подходов. И я обнаружил, что оба подхода дают одинаковый и правильный ответ в первом примере, который я предоставил T(n) = 3T(n/4) + c*n^2, но не во втором примере T(n) = T(n/2) + T(n/4) + T(n/8). Может кто-нибудь указать, где моя ошибка или недоразумение?
Извините за длинный вопрос, и мне все еще не разрешено напрямую включать фотографии в мой вопрос Спасибо за ваше время!