Majorations de complexité

piRo0

Je sens que je vais choquer (ou peut être tout simplement ne pas interesser) les adeptes de la rigueur absolue du monde mathématique en vous proposant une inégalité un peu douteuse.

Je m'explique, il s'agit de majorer la complexité d'un programme informatique:

la complexité (C) en fonction de la taille de la donnée à traiter (n) vérifie l'inégalité:

C(n) < a*n+C(partie_entière(n/5))+C(7*partie_entière(n/10)+4)

et on demande de montrer que, pour n suffisamment grand (le genre de précisions que j'adore), on a C(n) < k*n ou k est une constante qui devrait s'exprimer en fonction de a.

J'ai tenté de résoudre la récurrence dans le cas d'égalité (pour avoir le comportement asymptotique): je remplace n par 5^p et j'espérai obtenir une récurrence linéaire. Le probleme c'est que je me retrouve avec du C(7*5^(p-2)+4) et que je ne vois vraiment pas comment ecrire ça comme un terme de la suite C(5^p).

J'avais déja posté un message demandant si quelqu'un avait une méthode de résolution des récurrences linéaires, j'ai trouvé un cours sur internet, mais maintenant que j'ai pu avancer dans le devoir, je tombe sur ce machin qui n'a pas vraiment l'air linéaire.

Miam miam...

Said6

<!--latex-->Bonjour
<BR>
<BR><!-- MATH $C(n) < a.n+C(E(n/5))+C(7E(n/10)+4)$ --><IMG WIDTH="315" HEIGHT="31" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2005/04/23/57063/cv/img1.png&quot; ALT="$ C(n) < a.n+C(E(n/5))+C(7E(n/10)+4)$">
<BR>
<BR><!-- MATH $C(n)<a.n+C(n/5)+C(7n/10+4)$ --><IMG WIDTH="265" HEIGHT="31" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2005/04/23/57063/cv/img2.png&quot; ALT="$ C(n)<a.n+C(n/5)+C(7n/10+4)$"> car<!-- MATH $E(x)\leq x$ --><IMG WIDTH="69" HEIGHT="31" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2005/04/23/57063/cv/img3.png&quot; ALT="$ E(x)\leq x$">
<BR>
<BR>
<BR><!-- MATH $C(n)<[a+C(1/5)+C(7/10)]n+4C$ --><IMG WIDTH="271" HEIGHT="31" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2005/04/23/57063/cv/img4.png&quot; ALT="$ C(n)<[a+C(1/5)+C(7/10)]n+4C$">
<BR>
<BR>Et donc <!-- MATH $C(n)\leq C'n$ --><IMG WIDTH="86" HEIGHT="31" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2005/04/23/57063/cv/img5.png&quot; ALT="$ C(n)\leq C'n$"> pour <IMG WIDTH="14" HEIGHT="14" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2005/04/23/57063/cv/img6.png&quot; ALT="$ n$"> assez grand
<BR>
<BR>Said<BR>

piRo0

Alors merci d'avoir répondu mais il y a deux trois trucs que je comprends pas dans ce que tu as fait ( ou alors c'est moi qui ait mal posé ma question, je sais pas):

Déja ce qui m'embête un peu dès la deuxième ligne c'est que, comme C(n) est une suite numérique, les nombres C(n/5) et compagnie (i.e quand tu enlèves la partie entière) n'ont pas nécéssairement de sens. Donc je me demande si ce qui suit est valable pour tout n ou seulement pour les multiples de 10.

Et après je ne comprends plus du tout: C est une suite, et pas une constante intervenant multiplicativement dans l'inégalité: je ne vois pas ce que signifie le 4*C en fin de ligne.

Si C était linéaire, on aurait le droit de faire un truc du genre mais ce n'est, à priori pas le cas. Et enfin, les nombres C(1/5), C(7/10) n'ont pas de sens.

Pierre

Said6

OK
je suis désolé
tout j'ai ecrit est faux

Said