Вопрос:
У меня возникают проблемы с этим рецидивирующим отношением.
T (n) = 2T (n/2) + 1
Может ли кто-нибудь помочь мне в объяснении того, как можно было бы решить это, чтобы получить ответ O(n)?
Лучший ответ:
Предположим для простоты, что n является степенью 2. Например, если n = 8 и базовый случай T(0) = 0 то дерево рекурсивного вызова выглядит так:
1 n = 8, depth 0 / / / / / / / / / / / 1 1 n = 4, depth 1 / / / / / / / / / / 1 1 1 1 n = 2, depth 2 / / / / / / / / 1 1 1 1 1 1 1 1 n = 1, depth 3 / / / / / / / / 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n = 0, depth 4
Дерево имеет log(n) + 1 уровней, не считая самого низкого уровня, потому что каждый узел этого уровня имеет стоимость 0. Чтобы вычислить T(n), в этом случае T(8), вы должны суммировать все единицы в дереве.
Обратите внимание, что на глубине i есть 2^i узлы, каждая из которых стоит 1.
Таким образом, формула для суммы единиц в дереве:
sum [from я = 0 to log(n)] 2^i
это геометрический ряд с a_1 = 1 и q = 2, и вы хотите знать сумму первых значений log(n) + 1. Это дается формулой:
(1 — 2^(log(n) + 1))/(1 — 2) = 2n — 1
Таким образом, для n = 8 результат равен 15.
Я надеюсь, это поможет вам.
Ответ №1
Хорошее объяснение таких отношений дано в Cormen et al. “Введение в альтогоизм”. Основная теорема 4.1 в этой книге рассматривает все рекуррентные соотношения вида T (n) = aT (n/b) + f (n). для различных комбинаций f, a и b. Один из случаев в этой теореме, случай 2. может быть применен к вашему примеру, давая оценку O (n). Итак, чтобы ответить на ваш вопрос, вы не можете просто решить такое отношение в смысле выполнения некоторых рутинных вычислений, чтобы закончить с асимптотикой, а вы заметили, что ваша ситуация относится к классу отношений, для которых существует оценка.
Ответ №2
Этот тип рекурсий решается с использованием теоремы Мастера.
В вашем случае a = 2, b = 2 и f(n) = 1. Итак, c = log2(2) = 1 и O(n^1) > O(1), что означает, что мы приходим в третий случай, и поэтому сложность O(n).
