Forum Prepas.org

P'tite blague au passage mdr

Enfin bref, quelqu'un peut m'expliquer c'est quoi et comment on calcul la complexité spatiale svp ?

Imaginons que tu veuilles calculer un certain résultat R.

La complexité spatiale, c'est la place dont tu as besoin en mémoire pour calculer R.
La complexité temporelle, c'est le nombre d'opérations dont tu as besoin pour calculer R.

Il faut avoir en tête qu'on ne sait pas résoudre certains problèmes pour des raisons de complexité. Certaines résolutions prendraient plusieurs milliers d'années avec tous les ordinateurs branchés ensemble (complexité temporelle très élevée). De même si on prend l'exemple d'une suite récurrente où on a besoin de connaître tous les termes depuis le début pour calculer un nouveau terme; plus on avance plus on a besoin de place pour stocker tous les termes de la suite, jusqu'à ce qu'on arrive au moment où on plus assez de place sur son ordinateur...
Bref la complexité est une notion importante pour confronter un algorithme théorique à sa mise en pratique. Et pour être plus précis on a simplement cherché à quantifier comment évolue la complexité (logarithmique, linéaire, quadratique...).

Pour la méthode de calcul de complexité. J'imagine que tu as une fonction qui a un paramètre qui prend des valeurs entières (n). Le principe est alors de déterminer combien de variables on stocke (pour la complexité spatiale) en fonction de n. Si on a une boucle par exemple, on peut decomposer chaque étape de la boucle...

Plusieurs milliers d'années c'est optimiste. Certains calculs demanderaient l'âge de l'univers puissance l'âge de l'univers pour être réalisés.

La complexité en temps et en espace n'a rien à voir avec "python".
Python c'est un langage.
Chaque *algo* a sa complexité en temps et en espace (complexité moyenne, ou pire cas...)

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).

(avec la bonne tabulation)

def exponentiation_naive(a,n):
____b = 0
____for i in range(n):
________b = b*a
____return b