Lorsque nous devons résoudre un problème et que de nombreux moyens sont disponibles pour résoudre ce problème (par exemple, problème de multiplication de chaîne matricielle), une analyse de l’algorithme est alors nécessaire.

L’analyse des algorithmes signifie estimer leur complexité dans un sens asymptotique. Le terme « analyse des algorithmes” a été inventé par Donald Knuth. L’analyse des algorithmes est la détermination de la quantité de ressources en temps et en espace nécessaires à son exécution.

La plupart des algorithmes sont de nature récursive, ils utilisent la stratégie diviser pour régner. L’algorithme récursif s’appelle lui-même pour les autres entrées. Cela fait généralement partie de l’entrée d’origine mais a une taille plus petite (sous-problème). Il existe de nombreuses façons de résoudre la relation de récurrence. Ils sont les suivants :

1. Théorème principal

2. Méthode de l’arbre de récurrence

3. Méthode de substitution

4. Changement de méthode de variable

Parmi toutes ces méthodes, le théorème principal est la méthode la plus rapide pour trouver la complexité temporelle de la fonction. Il est très facile à comprendre et facile à appliquer. Nous devons juste nous souvenir de certains cas. Alors voilà.