Python m'expliquer la complexité spatiale et temporelle ?

Modérateur : Michel Quercia

Répondre
Nefi
Messages : 31
Enregistré le : ven. mai 25, 2018 2:02 am

Python m'expliquer la complexité spatiale et temporelle ?

Message par Nefi » dim. nov. 04, 2018 6:59 pm

P'tite blague au passage mdr :(

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

Avatar du membre
siro
Messages : 3226
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

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

Message par siro » dim. nov. 04, 2018 9:18 pm

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.

Avatar du membre
Poliakoff
Messages : 350
Enregistré le : mar. juil. 18, 2017 2:16 pm
Classe : PC*
Localisation : Lyon

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

Message par Poliakoff » dim. nov. 04, 2018 11:51 pm

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

Avatar du membre
siro
Messages : 3226
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

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

Message par siro » lun. nov. 05, 2018 12:49 am

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.

Avatar du membre
fakbill
Messages : 11166
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

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

Message par fakbill » mer. nov. 07, 2018 12:35 pm

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

Aubyn Kensington
Messages : 11
Enregistré le : mar. sept. 25, 2018 3:07 pm
Classe : MP

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

Message par Aubyn Kensington » sam. nov. 10, 2018 12:17 am

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

Aubyn Kensington
Messages : 11
Enregistré le : mar. sept. 25, 2018 3:07 pm
Classe : MP

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

Message par Aubyn Kensington » sam. nov. 10, 2018 12:18 am

(avec la bonne tabulation)

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

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité