Soit ensuite l’algorithme suivant :
Début
Soit
x ← 5
y : tableau indexé vide
n ← 10
Pour toutes les valeurs de i comprises entre 1 et n par pas de 1, faire
ajouter à y : x + ( 5 * i )
Fin Pour
FinComme avant, le coût temporel de cet algorithme est linéaire. Il est dépendant de la valeur de n.
Ce coût comprend :
> deux affectations initiales
> n incrémentations de i, n multiplications, n additions et n ajouts de valeur à y.
> soit c = 4n + 2, c étant le coût.
Le coût spatial est lui aussi linéaire, et dépend également de la valeur de n. Il comprend :
> une partie constante : k.o (3 affectations pour x, n et i et 1 adressage en RAM pour y)
> une partie variable : n.o pour les valeurs stockées dans y
CQFR : Ce Qu’il Faut Retenir (donc apprendre !)…
D’une façon générale, le coût est dit linéaire lorsqu’il s’exprime mathématiquement de la manière suivante : C = a.x + b, a.x correspondant au coût d’une séquence d’instructions sur laquelle on réalise une itération et b au coût des instructions sur lesquelles on ne réalise aucune itération.
ct : coût temporel ; ct = a.n + b, ou a est un nombre d’opérations répétées n fois et b un nombre constant d’opérations ;
cs : coût spatial ; cs = a.n + b, ou a est le nombre d’octets nécessaires pour stocker une donnée n fois en RAM et b un nombre constant d’octets correspondant au stockage d’un nombre fixe de données.
<< Cliquez pour plus d’informations <<