Почему стоимость в дереве рекурсии показана как дополнение?

Я знакомлюсь с алгоритмами и пытаюсь немного больше понять деревья рекурсии (я использую учебник CLRS). Вот примерный алгоритм:

 T(n) = 3T(n/4) + cn^2

Насколько я понимаю, 3T(n/4) представляет количество рекурсивных подзадач и то, что они делают. Для этого примера алгоритма каждая рекурсия делит массив (n/4). С 4 подзадачами, как показано цифрой 4 перед буквой T. cn^2 — это стоимость выполнения этого уровня рекурсии в дереве.

Итак, со всем этим у меня возникла проблема при попытке построить дерево рекурсии: < img src="https://i.stack.imgur.com/P8hZ7.png" alt="введите здесь описание изображения" />

Почему на шаге c этого изображения дети, похоже, наследуют форму cn^2?? Я думал, что cn^2 — это просто стоимость первого шага? Знак сложения в исходном уравнении T (n) сбивает меня с толку, почему это представлено как сложение, а затем в дереве к каждому шагу применяется форма cn ^ 2? Не будет ли это больше похоже на умножение?

Ищем интуитивные ответы.


recursion runtime tree clrs
person sdub0800    schedule 12.09.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Давайте быстро изменим обозначения. Вместо использования T(n) назовем его T(k). Это дает нам отношение

T(k) = 3T(k / 4) + ck2.

Идея здесь в том, что T(k) означает общий объем работы, проделанной при оценке рекурсивного вызова на входе размера k. Если вы изначально запускаете рекурсию, вызывая рекурсивную функцию для входных данных размера n, вам будет интересно вычислить T(n).

Причина, по которой я считаю полезным изменить имя переменной на k, состоит в том, чтобы прояснить, что происходит. T(k) – это общая формула для определения объема работы, необходимой для оценки повторяемости входных данных размера k. Здесь k — переменная-заполнитель. Вы можете спросить, что такое T(137), чтобы увидеть, сколько работы выполняется на входе размера 137, или вы можете спросить, что такое T(2m), если вам интересно, как масштабируется работа. когда вход представляет собой совершенную степень двойки.

Теперь давайте проанализируем, что говорит формула. Формула T(k) = 3T(k / 4) + ck2 говорит, что работа, необходимая для вычисления функции на входе размера k, определяется следующим образом:

  • Некоторый базовый объем работы, выполняемый рекурсивным вызовом верхнего уровня. Эта сумма составляет ck2.
  • Некоторый объем работы требуется рекурсивными вызовами. В частности, есть три рекурсивных вызова, каждый из которых относится к входным данным, размер которых составляет четверть размера оригинала.

Давайте попробуем это на примере. Что такое Т(16)? Что ж, это будет c(162) = 256c плюс 3T(16/4) = 3T(4). То есть:

T(16) = 256c + 3T(4).

Теперь, что такое T(4)? Итак, c(42) = 16c плюс 3T(4/4) = 3T(1). Таким образом, у нас есть

T(4) = 16c + 3T(1),

и объединение этого с тем, что у нас есть выше, дает

T(16) = 256c + 3(16c + 3T(1)) = 256c + 48c + 9T(1) = 304c + 9T(1).

Вы видите, как, прорабатывая каждый шаг, мы передаем меньшее значение k? Вот что происходит, когда мы оцениваем повторение. Каждое отдельное значение T(k) всегда добавляет некоторую функцию от k, а значение k, которое оно наследует, определяется рекуррентностью.

Надеюсь, это поможет — дайте мне знать в комментариях, если есть что-то еще, что я могу прояснить!

person templatetypedef    schedule 12.09.2020