Python m'expliquer la complexité spatiale et temporelle ?

Messages : 0

Inscription : 25 mai 2018 02:02

Profil de l'utilisateur : Élève de lycée

Python m'expliquer la complexité spatiale et temporelle ?

Message par Nefi » 04 nov. 2018 17:59

P'tite blague au passage mdr :(

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

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Python m'expliquer la complexité spatiale et temporelle ?

Message par siro » 04 nov. 2018 20:18

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.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 0

Inscription : 18 juil. 2017 14:16

Profil de l'utilisateur : Élève de lycée

Re: Python m'expliquer la complexité spatiale et temporelle ?

Message par Poliakoff » 04 nov. 2018 22:51

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...
"On va spontanément d'une situation ordonnée vers une situation désordonnée, c'est la flèche du temps."

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Python m'expliquer la complexité spatiale et temporelle ?

Message par siro » 04 nov. 2018 23:49

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.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Python m'expliquer la complexité spatiale et temporelle ?

Message par fakbill » 07 nov. 2018 11:35

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...)
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 4

Inscription : 25 sept. 2018 15:07

Profil de l'utilisateur : Élève de lycée

Re: Python m'expliquer la complexité spatiale et temporelle ?

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

Messages : 4

Inscription : 25 sept. 2018 15:07

Profil de l'utilisateur : Élève de lycée

Re: Python m'expliquer la complexité spatiale et temporelle ?

Message par Aubyn Kensington » 09 nov. 2018 23:18

(avec la bonne tabulation)

def exponentiation_naive(a,n):
____b = 0
____for i in range(n):
________b = b*a
____return b
모사재인 성사재천
MPSI -> MP -> CentraleSupélec

Répondre