Divide and conquer

[fatal_error]

hi all,

j'ai une suite t(n) = t(n/2)+t(n/3)
je voudrais calculer son terme général. (pas sa complexité)
mettons t(0) = t(1) = 1

dans le cas où u(n)=u(n/2) je sais que je peux opérer le changement de variable w=2^n, mais ici?

[jonses]

Salut !

Un peu en réflexion à la va-vite, je pense au changement de variable

Je vais essayer de voir ce que ça donne.

[GaBuZoMeu]

j'ai une suite t(n) = t(n/2)+t(n/3)
je voudrais calculer son terme général. (pas sa complexité)
mettons t(0) = t(1) = 1

J'ai du mal à voir le sens de cette question telle que tu la formules. Déjà, n/2 et n/3 n'ont aucune raison d'être des entiers.
Vu le titre que tu as choisi, je comprends que tu cherches à estimer la complexité d'un algorithme de type de type diviser pour gagner, avec la propriété que la complexité pour une taille n d'entrée est égale à la somme de la complexité pour une taille n/2 et de la complexité pour une taille n/3

dans le cas où u(n)=u(n/2) je sais que je peux opérer le changement de variable w=2^n, mais ici?

Dans ce cas là, la complexité est constante ! Tu n'as sans doute pas écrit ce que tu voulais écrire.

[GaBuZoMeu]

Bon, pour ne pas être entièrement négatif : une représentation graphique de la suite définie par , et pour , .

Code: Tout sélectionner

L=[(0,1),(1,1)]
for i in range(2,2000) :
    L.append((i,L[(i/2).ceil()][1]+L[(i/3).ceil()][1]))
line(L)

C'est sous-linéaire, bien sûr.

[fatal_error]

Dans ce cas là, la complexité est constante !

J'étais pas clair dans l'idée que je voulais transmettre:

Si on considère (pour éviter le cas constant...)

en posant par , , et
d'où et en passant au logarithme base 2, , ce qu'on vérifie rapidement pour les puissances de 2:
u(1) = 1
u(2) = u(1) + 1 = 2
u(4) = u(2) + 1 = 3
u(8) = u(4) + 1 = 4
...
et d'autre part

pour autant, u(n) est définie pour tout n (positif) et "recolle" bien pour les puissances de 2.
l'idée que je voulais montrer c'est que même si on a une relation que pour les n divisibles par deux, on a pu "interpoler" pour tout n.
J'imagine qu'on peut avoir la même chose pour

J'ai du mal à voir le sens de cette question telle que tu la formules. Déjà, n/2 et n/3 n'ont aucune raison d'être des entiers.

est-ce que ci-dessous va mieux?

t(n) = t(n/2) + t(n/3) si n%6 = 0
t(n) = t((n-k)/2) + t((n-k)/3) si n%6 = k (k different de 0)
les conditions intiales au choix, mais on peut dire dans la continuité (sans jeu de mots voulu...): t(n) = 1 pour n=0 à 5

edit: nos messages ce sont croisés.
à choisir je prendraiS le floor plutot que le ceil, (dans le sens où pour diviser n par 2, si n vaut 5, j'admettrais n == 4). Dans mes modulo 6 je suis un peu plus grossier pour la simplification mais effectivement on peut être plus précis

[GaBuZoMeu]

Code: Tout sélectionner

L=[(0,1),(1,1),(2,1),(3,1),(4,1),(5,1)]
for i in range(6,2000) :
    n=(i/6).floor()
    L.append((i,L[2*n][1]+L[3*n][1]))
line(L)

[fatal_error]

Je ressssens le python en toi
partons sur la def de t(n) ci-dessous
t(n) = t((n-k)/2) + t((n-k)/3) avec n%6=k
t(n) = 1 si n<=5

si elle est correcte, peut-on avoir un terme général de t(n)?

[GaBuZoMeu]

Tu as vu la tête de la représentation graphique ?
Il me semble plus raisonnable de trouver une majoration qui précise le comportement sous-linéaire.
J'aurais un faible pour .
Je te laisse voir pourquoi.