Niveau Licence Maths 1e ann

Demande

Posté par
toureissa 12-05-18 à 14:26

Bonjour,

Je demande aux modérateurs s'il est possible d'avoir d'aide sur un exercice de programmation dans l'espace "EXPRESSO"?

Posté par re : Demande 12-05-18 à 14:29

Ben oui ! quel exercice ?
Et pourquoi au juste tu veux le mettre dans le forum expresso ?

Posté par re : Demande 12-05-18 à 14:33

Merci!

Posté par Majoration et Complexité 12-05-18 à 14:42

ReBonjour,

Voici l'exercice . j'ai besoin d'aide pour faire le première ensuite je vais essayer les autres.

Pour chacune des fonctions ci-dessus, donner une fonction qui la majore et en déduire sa classe de complexité.

$a)\; f(n)=n^4+25n^3+4$

$b)\; g(n)=14n^2+3^n$

$c)\; h(n)=4n^2+10n+5^n+2log(n)$

$d)\; k(n)=(3n+1)log(n)+3^n$ .

Merci d'avance !

*** message déplacé *** on se demande pourquoi tu veux qu'il soit dans Expresso ? ***
*** je vais le déplacer ***

Posté par re : Demande 12-05-18 à 17:31

Bonsoir toureissa.

Qu'entends tu par « classe de complexité » ?

En particulier je ne vois pas en quoi connaître une majoration d'une fonction donnerait des indications sur la complexité du calcul.

Posté par re : Demande 12-05-18 à 19:57

Bonjour, je ne vois pas l'intérêt de majorer ces fonctions pour déterminer leur "classe de complexité". Si je note X > Y pour dire X est prépondérant sur Y, on a :

exponentielle > puissance > quasi-linéaire> linéaire > logarithmique > constant

Il est alors facile de déterminer les classes de complexité en regardant le type des termes dominants. Par exemple f est de classe quartique car le n $4$ est prépondérant sur le terme en n³ lui-même prépondérant sur le terme constant.