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))\).