Récurrence

8

Remarque: ceci provient des notes d'Algorithmes de JeffE sur les récurrences, page 5.

(1). Nous définissons donc la récurrenceT(n)=nT(n)+nsans aucun cas de base. Maintenant, je comprends que pour la plupart des récidives, puisque nous recherchons des limites asymptotiques, le cas de base n'a pas d'importance. Mais dans ce cas, je ne vois même pas où nous pourrions définir le cas de base. Y a-t-il un nombre que nous sommes assurés d'atteindre alors que nous continuons à prendre des racines carrées à partir de n'importe quel entier Définissons-nous simplementT(n)=une pour n<b, pour certains reals une, b?

(2). À la page 7, Erickson obtient que le nombre de couches dans l'arbre de récursion L satisferan2L=2. D'où cela vient-il? Je n'ai aucune idée. Je vois que le nombre de feuilles dans l'arbre doit être égal à(n)(n)=n, mais je ne sais pas où aller à partir de là.

Toute aide est appréciée!

Notes que je regarde: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

DB Cooper
la source

Réponses:

7

Vous devriez vraiment poser une troisième question: que se passe-t-il si nn'est pas un carré parfait. La réponse à cette question est que la récurrence réelle aurait dûT(n) ou T(n) au lieu de T(n), bien que dans l'analyse, nous ne considérerons que les entrées qui sont des carrés "récursifs".

Concernant votre première question, il peut y avoir plus d'un cas de base. Par exemple, peut-êtreT(n)=1 pour tous n100. Vous êtes assuré de toucher éventuellement ce cas de base. Dans ce cas, comme dans la plupart des cas, la forme exacte du cas de base n'affecte pas les grandes asymptotiques Thêta (mais elle affecte la constante cachée).

Enfin, concernant votre deuxième question, supposons que votre cas de base spécifie T(n) pour nC. L'arbre de récursivité (qui est une interprétation particulière de certaines caractéristiques de la récurrence) a la forme suivante:

  • La racine est une instance de taille n.
  • La racine a n les enfants qui sont des instances de taille n.
  • Chaque nœud à la profondeur 1 a n=n1/4 les enfants qui sont des instances de taille n=n1/8.
  • Plus généralement, un nœud en profondeur d est une instance de taille n1/2d. Vous pouvez le prouver par induction en vérifiant le casd=0 (où n1/2d=n) et calcul n1/2d=n1/2d+1.

La récursivité se termine lorsque l'instance a une taille maximale C, et cela se produit lorsque n1/2dC. Au moment où cela se produit, nous avonsn1/2d1>C (en supposant n>C), et donc C<n1/2dC. Prenant le logarithme,12JournalC<Journaln2<JournalC et donc Journaln2=Θ(1), impliquant 2=Θ(Journaln). Nous pouvons conclure queJournalJournaln. Il s'agit du nombre de couches dans l'arbre. Jeff utiliseC=2, c'est ainsi qu'il obtient sa formule particulière.

Yuval Filmus
la source
4

Répondre à votre première question. Alternative à l'utilisation de la borne supérieure et de la borne inférieure pour obtenir un scénario de base, une option consiste à prendre la forme den.

Prenons, par exemple, la récursion mergesort:

T(n)=2cT(n2)+cn

De toute évidence, la plupart nne se divisera pas également en nombres entiers. Il est alors assez courant de supposer quen est de la forme:

n=2kkN

Cela implique que chaque n est une puissance positive de 2, résolvant ainsi notre cas de base toujours 1. Alternativement, nous pourrions faire le cas de basec au lieu de 1 en supposant n est de la forme:

n=c2kkN,cN+

Nous pouvons appliquer cela à notre récurrence:

T(n)=nT(n)+n

Présumer n est de la forme:

n=c2kkN,cN+
Ensuite, le cas de base se résoudra toujours en une constante c.

Maintenant, si vous pouvez le prouver sous cette hypothèse, vous pouvez ensuite faire une preuve pour nvaleurs qui n'ont pas cette forme. Une approche consisterait à tenter de le délimiter par le prochain plus haut (ou le plus bas)nqui n'ont cette forme.

ryan
la source