Message
par Aubyn Kensington » 09 nov. 2018 23:17
Pour expliquer en une phrase, la complexité spatiale correspond à l'espace de mémoire qu'on dont on a besoin, et la complexité temporelle le temps d'exécution du programme.
Lors de l'exécution d'un programme, la machine a ce qu'on appelle un « État », qui est l'ensemble des variables considérés dans la séquence de code. Faire une estimation de complexité spatiale, c'est calculer l'espace dont on a besoin pour faire exécuter le programme.
La complexité spatiale est rarement demandé au concours, mais il faut savoir ce dont il s'agit. Lorsqu'on demande une estimation de complexité, on sous-entend « estimation de complexité temporelle ».
On considère qu'il existe une classe d'opérations dite « élémentaires » (l'addition, la soustraction, la multiplication, le modulo, l'affectation de valeur etc.). On fait la simplification qu'une opération élémentaire prend un temps constant pour se faire, indépendamment des paramètres qu'elle prend en argument (ce qui n'est qu'une simplification. 1+1 prend évidemment moins de temps à calculer que 38394*49792, mais les deux sont des expressions correspondant à des opérations élémentaires).
Faire une estimation de complexité temporelle, c'est calculer le nombre d'opération élémentaires faites lors de l'exécution d'un programme. Plus exactement, une fonction ou un procédure prend en argument un nombre de fini de paramètre, dont dépend la complexité. (la complexité dépend de un ou deux paramètres dans 99 pourcent des cas).
Lorsqu'on te demande de faire une estimation de complexité temporelle, il faut, avec une notation de Landau « le grand O », majorer le nombre d'opération élémentaires (et non pas de compter combien il y d'addition, de multiplication, d'affectation etc).
Sauf indication contraire dans l'énoncé, lorsque le sujet parle de complexité, on sous-entend « complexité dans le pire des cas ». (et non pas la complexité dans le meilleur des cas , ou la complexité moyenne).
un petit exemple : le calcul d'exponentiation.
On écrit une fonction prenant en entrée un réel a et un naturel n, et qui renvoie a puissance n.
On initialise un variable b à 1, et on réitère n fois l'opération « affecter à b la valeur b fois a », et enfin on renvoie b. En python:
def exponentiation_naive(a,n):
b = 0
for i in range(n):
b = b*a
return b
Dans chaque itération du boucle « for », on réalise deux opérations élémentaires : une affectation et une multiplication. Donc chaque itération est de complexité constante (O(1) en notation de Landau). Il y a au total n itération dans le boucle for, donc la complexité de la séquence de code est O(n).
모사재인 성사재천
MPSI -> MP -> CentraleSupélec