Niveau algorithmique

preuve trèèèès difficile

Posté par
mateo1234 07-04-18 à 03:41

Bonsoir à tous ,

je dois déterminer si cette expression est vraie ou fausse puis prouver ma reponse par une preuve ...

je me retrouve un peu face au mur et je demande donc votre aide si vous pourriez me guider vers une solution possible ? voici le problème en question :

Si les fonctions g et h sont croissantes, alors g ◦ h(n) ∈ O(h ◦ g (n))

c'Est vrai ? c'est faux ? je trouve ca comment ? O_O

ps : voici la definition de O(g(n)) :
f(n) = O(g(n)) =⇒ ∃n1, c1 > 0/∀n ≥ n1,|f(n)| ≤ c1 * |g(n)|

merci beaucoup pour votre aide

Posté par une preuve très difficile en analyse d'algo 07-04-18 à 03:45

Bonsoir à tous ,

je dois déterminer si cette expression est vraie ou fausse puis prouver ma reponse par une preuve ...

je me retrouve un peu face au mur et je demande donc votre aide si vous pourriez me guider vers une solution possible  ? voici le problème en question :

Si les fonctions g et h  sont croissantes, alors g ◦ h(n) ∈ O(h ◦ g (n))

c'Est vrai ? c'est faux ? je trouve ca comment ? O_O

ps : voici la definition de O(g(n)) :
f(n) = O(g(n)) =⇒ ∃n1, c1 > 0/∀n ≥ n1,|f(n)| ≤ c1 * |g(n)|

merci beaucoup pour votre aide

*** message déplacé ***