Дерево рекурсии и метод подстановки

Question

У меня есть следующее упражнение:

"использовать дерево рекурсии, чтобы определить хорошую асимптотическую верхнюю границу рекуррентности T (n) = T (n / 2) + n ^ 2. Используйте метод подстановкипроверьте свой ответ "

Я создал это дерево рекурсии

Где я предположил, что k -> бесконечность (в моей книге они часто останавливают повторение, когдавход в T получает 1, но я не думаю, что это тот случай, когда у меня нет другой информации).

Я пришел к выводу, что:

Когда я использовал метод подстановки, я предположил, что T (n) = O (n ^ 2)

И затем сделал следующие шаги:

Когда n> 0 и c> 0, я вижу, что верно следующее для некоторого выбора c

И, следовательно, T (n) <= cn ^ 2 </p>

И мой вопрос: «Это правильный способ сделать это?»

Answer 1

Прежде всего, как сказал Филипп, ваше дерево рекурсии неверно. В конце концов, это не повлияло на сложность, но вы неправильно поняли константы.

T(n) becomes
n^2 + T(n/2) becomes
n^2 + n^2/4 + T(n/4) becomes
...
n^2(1 + 1/4 + 1/16 + ...)

Остановка на одном против остановки на бесконечности - это в основном дело вкуса и выбора того, что удобнее. В этом случае я бы сделал то же самое, что и вы, и использовал бы бесконечную сумму, потому что тогда мы можем использовать формулу геометрического ряда, чтобы получить правильное предположение, что T(n) <= (4/3)n^2

---

Единственное, что меня немного беспокоит, так это то, что ваше доказательство в конце концов склоняется к неформальному. Очень легко заблудиться в неофициальных доказательствах, поэтому, если бы мне пришлось оценивать ваше задание, мне было бы удобнее с традиционным доказательством по индукции, например, следующим:

заявление, чтобы доказать

We wish to prove that T(n) <= (4/3)*n^2, for n >= 1

Конкретные значения для c и n0 делают доказательства более достоверными, поэтому вставьте их, если можете. Часто вам нужно будет запустить доказательство один раз, чтобы действительно найти значения, а затем вернуться и вставить их, как если бы вы уже знали их в первую очередь :) В этом случае я надеюсь, что мое предположение 4/3 из дерево рекурсии получается правильным.

Доказательство по индукции:

Базовый случай (n = 1):

T(1) = 1 

(Вы не указали значение T (1) явно, но я думаю, это должно быть в первоначальном упражнении)

T(1)  = 1
     <= 4/3
      = (4/3)*1^2
T(1) <= (4/3)*1^2

Как мы и хотели.

Индуктивный корпус (n> 1):

(Здесь мы предполагаем индуктивную гипотезу T(n') <= 4/3*(n')^2 для всех n '

Мы знаем, что

T(n) = n^2 + T(n/2)

По индуктивной гипотезе:

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

Делаем алгебру:

T(n) <= n^2 + (4/3)(n/2)^2
      = n^2 + (1/3)n^2
      = (4/3)n^2
T(n) <= (4/3)*n^2

Как мы и хотели.

---

Может выглядеть скучно, но теперь я могу быть уверен, что я правильно понял!

Answer 2

Ваше дерево рекурсии ошибочно.Это должно выглядеть так:

n ^ 2|(П / 2) ^ 2|(П / 4) ^ 2|...|(n / 2 ^ k) ^ 2

Вы можете безопасно остановиться, как только T достигнет 1, потому что вы обычно подсчитываете дискретные «шаги», а такой вещи как «0,34 шага» не существует.

Поскольку вы делите n на 2 в каждой итерации, k здесь равно log2(n).