Analyse des algorithmes - Opérations élémentaires

On appelle opérations élémentaires les opérations suivantes

•  Un accès mémoire pour lire ou écrire la valeur d’une variable ou d’une case d’un tableau
•  Une opération arithmétique entre entiers ou réels telle que l’addition, soustraction, multiplication, division ou calcul du reste d’une division entière ;
•  Une comparaison entre deux entiers ou réels.

Exemple : 

L’instruction \(c = a + b\) nécessite les quatre opérations élémentaires suivantes :

•  Un accès mémoire pour la lecture de la valeur de a,
•  Un accès mémoire pour la lecture de la valeur de b,
•  Une addition de a et b,
•  Un accès mémoire pour l’écriture de la nouvelle valeur de c.

Nous voulons souvent raisonner sur le temps d'exécution d'une manière qui ne dépend que de l'algorithme et de son entrée. Ceci peut être réalisé en choisissant une opération élémentaire, que l'algorithme effectue à plusieurs reprises, et en définissant la complexité temporelle \(T(n)\) comme le nombre de ces opérations que l'algorithme effectue étant donné un jeu de données de longueur n.

En général, une opération élémentaire doit avoir deux propriétés:

•  Aucune autre opération ne peut être effectuée plus fréquemment au fur et à mesure que la taille de l’entrée augmente.
•  Le temps nécessaire à l'exécution d'une opération élémentaire doit être constant : il ne doit pas augmenter au fur et à mesure que la taille de l'entrée augmente. C'est ce que l'on appelle le coût unitaire.

Le coût unitaire et le coût en bits sont deux fonctions de coût différentes utilisées pour calculer la complexité den terme de l'espace et du temps

•  Le coût unitaire est utilisé dans un modèle simplifié où un nombre, de n'importe quelle taille, tient dans une case(ou cellule) de mémoire et où les opérations arithmétiques standard prennent un temps constant.
•  Avec un coût en bits, nous prenons en compte que les calculs avec de plus grands nombres peuvent être plus coûteuses.

Exemple de coût unitaire

def addition(x,y): # x et y sont des valeurs numériques
	return x+y
                                    

Dans cet exemple simple, il est judicieux d'utiliser le coût unitaire et de dire que la fonction s'exécute en temps constant.

Exemple de coût en bits

def concatener(x,y): # x et y sont des chaines de caractères ou tableaux
	return x+y
                                    

Ici, ce serait une erreur d'utiliser le coût unitaire pour l'opération + : pour concaténer deux chaînes de caractères, il faut allouer une nouvelle mémoire et copier les caractères.

Dans ce cas, il est préférable d'utiliser le coût en bits pour l'opération + :

•  La longueur des chaînes est utilisée pour mesurer la taille de l'entrée,
•  Et nous disons que la fonction fonctionne en temps \(\Theta(len(x) + len(y))\).