Изменение переменных в рекуррентных отношениях

20

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

Следующий метод может быть проиллюстрирован на этом примере. Предположим, у нас есть рецидив

T(n)=2T(n)+logn

Первоначально они делают замену m = lg (n), а затем подключают ее снова к повторению и получают:

T(2m)=2T(2m2)+m

До этого момента я прекрасно понимаю. Этот следующий шаг меня смущает.

Теперь они «переименовывают» рекуррентность и позволяют , что, по-видимому, приводит кS ( м ) = Т ( 2 м )S(m)S(м)знак равноT(2м)

S(м)знак равно2S(м/2)+м

По какой-то причине мне не понятно, почему это переименование работает, и это просто кажется обманом. Кто-нибудь может объяснить это лучше?

goooser
источник

Ответы:

15

Это конечно не обман. Подумайте в исчислении, как замена может быть использована для решения сложного интеграла. Подстановка делает уравнение более управляемым для манипуляций. Кроме того, замена может превратить несколько сложных повторений в знакомые.

Это именно то, что произошло в вашем примере. Определим новое повторение . Помните, что T ( 2 м ) = 2 T ( 2 м)S(м)знак равноT(2м). Обратите внимание, чтоS(м/2)=Т(2мT(2м)знак равно2T(2м2)+м. Если этот конкретный момент все еще неясен, пустьk=m/2и обратите внимание, что все, что мы делаем, этоS(k)=T(2k). Теперь мы можем выразитьS(m), расширив его до: S(m)=2S(m/2)+m. Решая дляS,мы видим, что он разрешается нашему знакомому другуO(mlogmS(м/2)знак равноT(2м2)Кзнак равном/2S(К)знак равноT(2К)S(м)

S(м)знак равно2S(м/2)+м,
S . Теперь, когда мы решили S, мы хотим выразить это через T ( n ) . Чтобы сделать это, просто вставьте обратно наше первоначальное значение для m, и мы получим T O ( log n log log n ) .О(мжурналм)ST(N)мTО(журналNжурналжурналN)
Николас Манкузо
источник
Хорошо, я полностью понимаю, как подстановка помогает облегчить проблемы и как вставить значения обратно, чтобы получить сложность с точки зрения n. Я предполагаю, что мой вопрос, после того, как вы позволили S (m) = T (2 ^ m), как вы получаете S (m / 2)? Это просто не очевидно для меня по какой-то причине. Чтобы быть более конкретным, как вы пришли к выводу, что T (2 ^ (м / 2)) = S (м / 2). Кажется, что в повторении T размер подзадачи имеет квадратный корень, в то время как в повторении S размер подзадачи уменьшается вдвое
Единственная часть, которую я не понимаю, это когда вы говорите: «Заметьте, что S (m / 2) = T (2 ^ (m / 2))». Это единственная часть, которая не очевидна для меня. Я привык к идее подстановки переменных, но на самом деле я не привык к идее подмены целого повторения.
Ах, хорошо, это последнее редактирование сделало это для меня. Теперь понятно, спасибо!
1
Я немного сомневаюсь. Если я пишу функцию S () в терминах kя получаю ниже уравнения S (к) = 2S (к / 2) + м Как я могу получить замену mдляk
Atinesh
4

S(м)знак равноT(2м)STм2м

S

  1. S'м2м

  2. T

Поэтому тогда переходы:

м2мT(2м)знак равноS(м)
м22м/2T(2м/2)знак равноS(м2),
Вивек Ананд Сампат
источник