Метод замещения для решения повторных обращений

Недавно у меня возникли проблемы с пониманием метода подстановки для решения повторений. Я просмотрел несколько онлайн-лекций о проблеме, но, к сожалению, они мало что рассказали мне (в одной из них я слышал, что она основана на предположениях, что еще больше сбило меня с толку), и я ищу несколько советов. Моя цель - решить три разные функции повторения с помощью метода подстановки, найти их временную сложность и их значения для T (32).

Function 1 is defined as:
T(1) = 1
T(n) = T(n-1) + n for n > 1

Я начал с перечисления первых нескольких казней:

T(2) = T(2-1)+2 = 1+2
T(3) = T(3-1)+3 = 1+2+3
T(4) = T(4-1)+4 = 1+2+3+4
T(5) = T(5-1)+5 = 1+2+3+4+5
...
T(n) = 1+2+...+(n-1)+n = n(n+1)/2

Затем я доказал по индукции, что Т (1) = 1, используя формулу для суммы первых натуральных чисел п, а затем, что это также верно для п + 1. Для меня это было довольно ясно, но я не уверен, что это метод подстановки. Также зная формулу Т (п) = п (п + 1) / 2, я легко вычислил T (32) = 528 и подсчитал временную сложность, которая составляет O (n ^ 2).

В примерах (2) и (3) мне нужно решение только для п = 2 ^ к, когда k - натуральное число, но было бы неплохо, если бы вы порекомендовали мне какие-либо статьи, показывающие, как получить их для всех п (но я полагаю, что это намного сложнее) .

Function 2 is defined as:
T(1) = 0
T(n) = T(n/2) + 1 for even n > 1
T(n) = T((n+1)/2) + 1 for odd n > 1

Поскольку мне разрешили доказать это только для п = 2 ^ к, и на основании полученных знаний я попытался сделать это следующим образом:

T(n) = T(n/2) + 1
     = T(n/4) + 1 + 1     = T(n/4) + 2
     = T(n/8) + 1 + 2     = T(n/8) + 3
     = T(n/16) + 1 + 3    = T(n/16) + 4
     = T(n/2^i) + i     // where i <= k, according to tutorials

И это момент, когда я застреваю и не могу двигаться дальше. Я полагаю, что мои расчеты верны, но я не уверен, как мне искать формулу, которая удовлетворяла бы этой функции. После того, как я получу правильную формулу, вычисление T (32) или временной сложности не будет проблемой.

Function 3 is defined as:
T(1) = 1
T(n) = 2T(n/2) + 1 for even n > 1
T(n) = T((n – 1)/2) + T((n+1)/2) + 1 for odd n > 1

Мои расчеты:

T(n) = 2T(n/2) + 1
     = 2(2T(n/4)+1) + 1 = 4T(n/4) + 3
     = 4(2T(n/8)+1) + 3 = 8T(n/8) + 7
     = iT(n/2^i) + 2^i - 1

И снова речь идет о формуле, которую я не знаю, как ее переписать.

По сути, означает ли метод подстановки для решения повторных ошибок поиск и итеративную формулу?

recursion

18.12.2018 04:08

Учебная записка [Medium] Leetcode#22 Generate Parentheses

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

459

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Пересмотрев тему, я обнаружил, что сделал не так, и, чтобы не оставлять свой вопрос без ответа, я постараюсь это сделать.

Первая функция рассчитана хорошо, индукционное доказательство тоже верно - тут нечего добавлять.

When it comes to the second function where I got stuck, I did not pay attention that I was actually using a substitution n=2^k. This is how it should look:

T(n) = T(n/2) + 1
     = T(n/4) + 1 + 1     = T(n/4) + 2
     = T(n/8) + 1 + 2     = T(n/8) + 3
     = T(n/16) + 1 + 3    = T(n/16) + 4
     = T(n/2^k) + k 
     = T(1) + k 
     = k

Доказательство индукции, что Т (2 ^ к) = к работает:
Базовый вариант: k = 1, тогда T (2 ^ 1) = T (2) = 1. (не может быть k = 0, так как 2 ^ 0 не больше 1)
Индуктивный шаг: предполагаем, что T (2 ^ k) = k, мы хотим показать T (2 ^ (k + 1)) = k + 1. Как 2 ^ к = п, то 2 ^ (к + 1) = 2 * 2 ^ к = 2n.

T(2n) = T(n) + 1
      = T(n/2) + 1 + 1
      = T(n/4) + 2 + 1
      = T(n/8) + 3 + 1
      = T(1) + k + 1
      = k + 1.

Временная сложность: O (лог. N)
Т (32) = Т (2 ^ 5) = 5

In the third function I missed that every time the function called itself, the value has doubled.

T(n) = 2T(n/2) + 1
     = 2(2T(n/4)+1) + 1     = 4T(n/4) + 3
     = 4(2T(n/8)+1) + 3     = 8T(n/8) + 7
     = 8(2T(n/16)+1) + 7    = 16T(n/16) + 15
     = 16(2T(n/32)+1) + 15  = 32T(n/32) + 31
     = 2^k*T(n/2^i) + 2^k - 1
     = 2^k*T(1) + 2^k - 1
     = 2^k + 2^k - 1
     = 2^(k+1) - 1

Доказательство индукции, что Т (2 ^ к) = 2 ^ (к + 1) -1 работает:
Базовый вариант: k = 1, тогда T (2 ^ 1) = T (2) = 3. Исходная функция T (2) = 2T (1) +1 = 2 + 1 = 3, поэтому базовый случай верен. Индуктивный шаг: предполагает, что T (2 ^ k) = 2 ^ (k + 1) -1, мы хотим показать T (2 ^ (k + 1)) = 2 ^ (k + 2) -1. Аналогично, как и во второй функции, 2 ^ к = п, поэтому 2 ^ (к + 1) = 2 * 2 ^ к = 2n.

T(2n) = 2T(n) + 1
      = 2(2T(n/2)+1) + 1    = 4T(n/2) + 3
      = 4(2T(n/4)+1) + 1    = 8T(n/4) + 7
      = 8(2T(n/8)+1) + 1    = 16T(n/8) + 15
      = 2^(k+1) + 2^(k+1) - 1
      = 2*2^(k+1) - 1
      = 2^(k+2) - 1.

Мы также могли бы взглянуть на первые несколько элементов для T (n), которые равны 1, 3, 5, 7, 9 и т. д., Поэтому T (n) = 2n-1

Временная сложность: О (н)
Т (32) = Т (2 ^ 5) = 2 ^ (5 + 1) - 1 = 64-1 = 63

18.12.2018 18:56