Approximation asymptotique d'une relation de récurrence (Akra-Bazzi ne semble pas s'appliquer)

10

Supposons qu'un algorithme ait une relation de récurrence d'exécution:

T(n)={g(n)+T(n1)+T(δn):nn0f(n):n<n0

pour une constante . Supposons que g est polynomial en n , peut-être quadratique. Très probablement, f sera exponentielle dans n .0<δ<1gnfn

Comment procéder pour analyser le runtime ( serait excellent)? Le théorème maître et la méthode plus générale d'Akra-Bazzi ne semblent pas s'appliquer.Θ

Austin Buchanan
la source
Trouver une bonne borne inférieure est facile mais trouver une bonne borne supérieure est difficile, mais grosso modo, il semble être proche de . T(n)=aT(n/a)+g(n)
1
Si vous cherchez encore une réponse, vous devriez vérifier Graham, Knuth et Patashnik, "Concrete Mathematics".
Kaveh
n0f
n0n0
1
J'ai posé une question connexe qui, jusqu'à présent, n'a pas présenté de théorème général pour des récurrences de ce type.
Raphael

Réponses:

5

T(n)=T(n)T(n1)T(n)T(n)

T(n)=T(δn)+g(n).
t(x)=t(δx)+g(x),
ddxt(x)=t(δx)+g(x).

t(x)

J'ai oublié tout ce que je savais sur les équations différentielles, donc je ne connais pas la solution de cette équation différentielle, mais peut-être pourrez-vous la résoudre en examinant toutes les techniques de résolution d'équations différentielles.

DW
la source
Donald J Newman semble avoir souvent utilisé cette technique, avec d'excellents résultats.
Aryabhata
t(x)