I ont 3 fonctions: f(n)=2n, g(n)=n! et h(n)=nlog(n) (log(n) est base 2).comportement asymptotique relative de ces fonctions
Comparaison f(n) et g(n): La fonction factorielle, g(n) peut être approchée en tant O(nn) (faible limite supérieure). Considérant ceci, est g(n)=Ω(f(n))? Comment comparer g(n) et h(n) et f(n) et h(n)?
(réponses peu profonde pour les devoirs)
Utilisez Stirling's approximation pour la fonction factoriel pour l'étudier est asymptotique. Pour la deuxième question, si vous avez des difficultés à étudier les fonctions telles qu'elles sont données, essayez d'en étudier les logarithmes. Ensuite, déduisez la relation entre les fonctions données sur la base des résultats que vous avez obtenus pour les logarithmes (ces résultats ne seront pas équivalents!)
Cela ressemble sûrement à des devoirs. – RBarryYoung
Presque un devoir. Je l'ai étiqueté ainsi, aussi bien. –
La réponse à votre première question est "non". L'inverse est vrai. 'f (n)' devient plus lent que 'g (n)'. Essayez d'utiliser la définition pour prouver des choses. –