Aproximação assintótica de uma relação de recorrência (Akra-Bazzi parece não se aplicar)

10

Suponha que um algoritmo tenha uma relação de recorrência em tempo de execução:

T(n)={g(n)+T(n-1 1)+T(δn):nn0 0f(n):n<n0 0

para alguma constante . Suponha que seja polinomial em , talvez quadrático. Muito provavelmente, será exponencial em .0 0<δ<1 1gnfn

Como alguém analisaria o tempo de execução ( seria excelente)? O teorema do mestre e o método mais geral de Akra-Bazzi parecem não se aplicar.Θ

Austin Buchanan
fonte
Encontrar um bom limite inferior é fácil, mas é difícil encontrar um bom limite superior, mas grosso modo parece estar próximo de . T(n)=umaT(n/uma)+g(n)
11
Se você ainda está procurando uma resposta, verifique Graham, Knuth e Patashnik, "Matemática Concreta".
Kaveh #
Supondo que seja constante, não precisamos de nenhuma suposição sobre , ou precisamos? fn0 0f
Raphael
O parâmetro pode ser específico da instância. Seria bom ver como o tempo de execução depende de . n 0n0 0n0 0
Austin Buchanan
11
Fiz uma pergunta relacionada que, até o momento, não trouxe nenhum teorema geral para recorrências desse tipo.
Raphael

Respostas:

5

Uma abordagem possível pode ser por analogia com equações diferenciais. Seja . Aqui T ( n ) é um análogo discreto da primeira derivada de T ( n ) . Temos a seguinte relação: T ( n ) = T ( δ n ) + g ( n ) .T(n)=T(n)-T(n-1 1)T(n)T(n)

T(n)=T(δn)+g(n).
O análogo contínuo disso é a equação diferencial ou, se você preferir vê-lo escrito de forma diferente: d
t(x)=t(δx)+g(x),
Essa é uma equação diferencial.
ddxt(x)=t(δx)+g(x).

t(x)

Eu esqueci tudo o que sabia sobre equações diferenciais, então não conheço a solução dessa equação diferencial, mas talvez você consiga resolvê-lo revisando todas as técnicas para resolver equações diferenciais.

DW
fonte
Donald J Newman parece ter usado essa técnica frequentemente, com ótimos resultados.
Aryabhata
t(x)