Exercice 2 : Analyse et démonstration de Complexité
Exercice 2 : Analyse et démonstration de Complexité
Soit \(p(n) = \sum_{i=0}^{p} a_i n^{i}\) un polynôme en \(n\) de degré \(p\) tel que \(a_d > 0\), où \(d\) est un entier, et soit \(k\) une constante. Montrer que si \(k \geq d\) alors \(p(n) = O(n^k)\).
Montrez que la borne asymptotique de la récurrence suivante est \(O(\log(n))\) : \(T(n) = T(n/2) + c\), où \(c\) est une constante.
Employer la méthode de substitution pour montrer que la récurrence \(T(n) = T(n-1) + \theta(n^2)\).
Méthode de l’arbre récursif : Dans un arbre récursif, chaque nœud représente le coût d’un sous-problème individuel, situé quelque part dans l’ensemble des invocations récursives de fonction. On totalise les coûts pour chaque niveau de l’arbre afin d’obtenir un ensemble de coûts par niveau, puis l’on cumule tous les coûts par niveau pour calculer le coût total de la récursivité tous niveaux confondus. Les arbres récursifs sont particulièrement utiles quand la récurrence décrit le temps d’exécution d’un algorithme diviser-pour-régner.
Employer la méthode des arbres pour montrer que la borne asymptotique approchée pour la récurrence \(T(n) = T(n/2) + \theta(1)\) associée à une recherche dichotomique est \(T(n) = \theta(\log(n))\).
CORRECTION :
....
Si vous avez trouvé les exercices corriges sur la Complexité des Algorithmes & Structure de donnée de Mr JoëlYk intéressants et utiles, pourquoi ne pas les partager avec d'autres personnes qui pourraient également en bénéficier ? Partagez ce lien sur les réseaux sociaux ou envoyez-le à vos amis et collègues. Vous pourriez aider quelqu'un à améliorer ses compétences en programmation ou à trouver des solutions à des problèmes complexes. N'oubliez pas que la connaissance doit être partagée pour grandir. Merci pour votre soutien et votre partage !
Contact WhatsApp : +237 658395978 | Réaliser Par Joël_Yk