Вопрос:
in или Data Structures мы изучаем, как решать рекуррентные отношения в 1 переменной. К сожалению, некоторые вещи кажутся “неожиданными”. Пример: некоторые упражнения уже говорят вам, как заменить переменную n:
Вычислить T (n) для n = 2 ^ k
T (n) = a при n = <2
T (n) = 8T (n/2) + bn ^ 2 (a и b → 0)
Но некоторые упражнения просто дают вам T (n), не предоставляя замену переменной n:
T (n) = 1 n = <1
T (n) = 2T (n/4) + sqrt (n)
Я использовал итерационный метод и пришел к правильному ответу: sqrt (n) + (1/2) * sqrt (n) * Log (n). Но когда профессор объяснил, что она начала говорить: “Пусть n = 4 ^ k”. Это то, что я подразумеваю под “неожиданностью”. Используя этот факт, ответ проще получить. Но как студент должен это придумать?
Это еще один пример:
T (n) = 1 n = <1
T (n) = 2T ((n -1)/2) + n
Здесь я снова начал с итерационного метода, но я не могу найти окончательного ответа, он выглядит более сложным. После 3 итеративных шагов я пришел к этому:
(1) T (n) = 4T ((n-2)/4) + 2n – 1
(2) T (n) = 8T ((n-3)/8) + 3n – 3
(3) T (n) = 16T ((n-4)/16) + 4n-6
Я склонен сказать, что T (i) = 2 ^ я * T ((ni)/2 ^ i) + я * n -??? , эта последняя часть, которую я не могу понять, может быть, я допустил ошибку.
Однако в ответ, который она дает, она снова начинает с другой подстановки: пусть n = (2 ^ k) -1. WTF??
Какова логика этого? Спасибо.
Лучший ответ:
Во всех этих случаях эти замены являются разумными, поскольку они переписывают рекуррент как один из форм S (k) = aS (k – 1) + f (k). Эти рецидивы часто легче решать, чем другие рецидивы, поскольку они определяют S (k) чисто в терминах S (k – 1).
Давайте сделаем несколько примеров, чтобы увидеть, как это работает. Рассмотрим это повторение:
T (n) = 1 (если n ≤ 1)
T (n) = 2T (n/4) + sqrt (n) (в противном случае)
Здесь размер проблемы сокращается в четыре раза на каждой итерации. Поэтому, если вход представляет собой идеальную мощность в четыре, тогда вход будет уменьшаться от размера 4 k до 4 k-1 от 4 k-1 до 4 k-2 и т.д. До тех пор, пока рекурсия не снизится. Если мы сделаем эту подстановку и пусть S (k) = T (4 k), то получим шляпу
S (0) = 1
S (k) = 2S (k – 1) + 2 k
Это теперь рекуррентное соотношение, где S (k) определяется через S (k – 1), что позволяет сделать рекурсию легче решить.
Давайте посмотрим на ваше первоначальное повторение:
T (n) = a (при n ≤ 2)
T (n) = 8T (n/2) + bn 2
Обратите внимание, что рекурсивный шаг делит n на два. Если n – совершенная степень двух, то рекурсивный шаг рассматривает степень двух, которая идет прямо перед n. Считая S (k) = T (2 k), получим
S (k) = a (при k ≤ 1)
S (k) = 8S (k – 1) + b2 2k
Заметим, что S (k) определяется в терминах S (k – 1), что намного проще повторять. Выбор полномочий двух был “естественным” здесь, потому что он сделал рекурсивный шаг, говоря только о предыдущем значении S, а не какое-то сколь угодно меньшее значение S.
Теперь посмотрим на последнее повторение:
T (n) = 1 (n ≤ 1)
T (n) = 2T ((n-1)/2) + n
Мы хотели бы сделать некоторую подстановку k = f (n) такой, что T (f (n)) = 2T (f (n) – 1) + n. Вопрос в том, как это сделать.
При некоторых проб и ошибок мы получаем, что настройка f (n) = 2 n – 1 соответствует счету, поскольку
(f (n) – 1)/2 = ((2 n – 1) – 1)/2 = (2 n – 2)/2 = 2 n-1 – 1 = f (n) – 1
Поэтому, полагая k = 2 n – 1 и полагая S (k) = T (2 n – 1), получаем
S (n) = 1 (если n ≤ 1)
S (n) = 2S (n – 1) + 2 n – 1
Надеюсь это поможет!
