Alterando variáveis ​​nas relações de recorrência

20

Atualmente, estou estudando Introdução aos Algoritmos (CLRS) e há um método específico que eles descrevem no livro para resolver as relações de recorrência.

O método a seguir pode ser ilustrado com este exemplo. Suponha que tenhamos a recorrência

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

Inicialmente, eles fazem a substituição m = lg (n) e, em seguida, conectam-na novamente à recorrência e obtêm:

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

Até este ponto, eu entendo perfeitamente. Este próximo passo é confuso para mim.

Eles agora "renomeiam" a recorrência e deixam , que aparentemente produzS(m)S(m)=T(2m)

S(m)=2S(m/2)+m

Por alguma razão, não está claro para mim por que essa renomeação funciona e parece apenas trapaça. Alguém pode explicar isso melhor?

goooser
fonte

Respostas:

15

Certamente não é trapaça. Pense em cálculo como a substituição pode ser usada para resolver uma integral complicada. A substituição torna a equação mais gerenciável para manipulação. Além disso, a substituição pode transformar recorrências um tanto complexas em familiares.

Foi exatamente isso que ocorreu no seu exemplo. Definimos uma nova recorrência . Lembre-se de que . Observe que, . Se esse ponto em particular ainda não estiver claro, deixe e observe que tudo o que estamos fazendo é este . Agora, podemos expressar expandindo-o para: Resolvendo para , vemos que isso resolve para o nosso amigo familiar . Agora que resolvemos , queremos expressar isso em termos de . Para fazer isso, basta reconectar nosso valor original paraS(m)=T(2m)T(2m)=2T(2m2)+mS(m/2)=T(2m2)k=m/2S(k)=T(2k)S(m)

S(m)=2S(m/2)+m.
SO(mlogm)ST(n)me temos .TO(lognloglogn)
Nicholas Mancuso
fonte
Certo, compreendo perfeitamente como a substituição ajuda a facilitar os problemas e como reconectar valores para obter a complexidade em termos de n. Acho que minha pergunta é: depois de deixar S (m) = T (2 ^ m), como você calcula S (m / 2)? É apenas não óbvio para mim, por algum motivo. Para ser mais específico, como você conclui que T (2 ^ (m / 2)) = S (m / 2). Parece que na recorrência T, o tamanho subproblema está sendo quadrado de raízes, enquanto na recorrência S, o tamanho subproblema está a ser reduzida para metade
A única parte que não compreendo é quando você diz "Observe que, S (m / 2) = T (2 ^ (m / 2))" Essa é a única parte que não é óbvia para mim. Estou acostumado com a ideia de fazer substituições variáveis, mas não estou acostumado com a ideia de substituir uma recorrência inteira.
Ah, ok, a última edição fez isso por mim. Está claro agora, obrigado!
1
Eu tenho um pouco de dúvida. Se eu escrever a função S () em termos de keu estou ficando abaixo da equação S (k) = 2S (k / 2) + m Como posso obter um substituto mparak
Atinesh
4

O meios é que e são duas funções diferentes que produzem o mesmo resultado, tendo entradas que e , respectivamente.S(m)=T(2m)STm2m

A função pode ser considerada como um operador com duas etapas internas (caso contrário, composição das funções):S

  1. SOperador : entrada: , saída:m2m

  2. TOperador (função original): Entrada: saída da primeira parte, Saída: Conforme definido originalmente.

Portanto, as transições são:

m2mT(2m)=S(m)
m22m/2T(2m/2)=S(m2).
Vivek Anand Sampath
fonte