Programmation Algorithmique/Nombre d'opérations optimal

Un livre de Wikibooks.

La rapidité d'un algorithme est exprimé sous la forme du nombre d'opérations effectué par celui-ci. En général, ce nombre dépend des données d'entrées.

Il existe différent nombres d'opération :

• le nombre d'opération minimal, qui se produit dans le meilleur des cas,
• le nombre d'opération maximal, qui se produit dans le pire des cas,
• le nombre moyen d'opérations, qui est une moyenne de ce que l'on peut espérer d'un algorithme dans la plupart des cas.

Exemple: Un algorithme de tri d'un tableau de n éléments effectuera un nombre moyen d'opérations dépendant de n (la taille du tableau) :

• L'algorithme de tri à bulle s'effectue en O(n²) ;
• L'algorithme de tri rapide (appelé Quicksort) s'effectue en moyenne en O(n*log(n)).

Sections 1 Comparaison de quelques algorithmes 1.1 Calcul de np 1.1.1 Algorithme simple 1.1.2 Algorithme plus complexe

[modifier] Comparaison de quelques algorithmes

[modifier] Calcul de n^p

But: Élever un nombre entier n à la puissance p (entier également).

[modifier] Algorithme simple

L'implémentation simple de cet algorithme est la suivante :

ENTIER resultat
resultat <- 1
pour i de 1 à p
faire
  resultat <- resultat * n
finfaire

Cet algorithme s'effectue en O(p)

[modifier] Algorithme plus complexe

Cet algorithme est plus complexe, mais effectue moins d'opérations que le précédent :

ENTIER resultat
resultat <- 1
tantque p > 0
faire
  si p ET 1 <> 0 alors          # test du bit 0 de p
    resultat <- resultat * n
  finsi
  n <- n * n
  p <- p / 2   # division entière ou décalage de bits
finfaire

Cet algorithme s'effectue en O(log(p))

Cet algorithme fonctionne de la façon suivante :

• A chaque itération de la boucle, n vaut successivement n, n², n⁴, n⁸, ...
• La valeur de l'exposant p en binaire s'exprime de la façon suivante :

• Chaque bit i de p est testé, s'il vaut 1, il faut multiplier le résultat temporaire par . La relation mathématique entre les puissances est utilisée. Par exemple : . Donc pour tous les bits de p, on a :