Discussion :

[barbsbou]

bonjour,

Lors d'un projet en C que j'ai du implementer avec un binome, nous devons etudier la complexite temps et memoire de notre algorithme. La complexite temps a été réalisé grace a la fonction clock() dans la librairie time.h.

En ce qui concerne l'etude de la complexite memoire je ne sais pas comment faire.
Auriez-vous une idee??


Merci d'avance.

[souviron34]

alors déjà la complexité temps n'EST PAS la mesure du temps...

C'est le facteur de proportionalité entre un nombre N de données et le temps que ça prend à faire le calcul.. La notation est O()

Même chose pour la mémoire...


C'est une mesure pour l'ALGORITHME (que tu pourrais faire sur le papier), pas sur l'IMPLANTATION et la mesure machine...


En gros : si tu fais une boucle : O(n), un tri (du style quick sort) : O(n log n), etc etc..

Pour la mémoire, tout dépend des structures, tableaux intermédiares, etc...

Pour N données , combien prenez vous de place mémoire lors de l'algo ?

[laconi87]

alors dans ce cas la existe t-il une fonction qui permettrer de connaitre la memoire prise pour pour effectuer le calcul. Ansi il serait ensuite possible de calculer le rapport invoquer: N/(Qte memoire utilse)

[Thierry Chappuis]

alors dans ce cas la existe t-il une fonction qui permettrer de connaitre la memoire prise pour pour effectuer le calcul. Ansi il serait ensuite possible de calculer le rapport invoquer: N/(Qte memoire utilse)

Je ne vois pas le besoin d'utiliser une fonction pour étudier la complexité mémoire d'un algorithme. Comme l'a dit souviron34, ce n'est pas un problème de C, mais l'algorithmique. Une feuille de papier et un crayon suffisent à cette analyse. Le forum adapté pour discuter de cette question est: http://www.developpez.net/forums/forumdisplay.php?f=60

Thierry

[barbsbou]

bonjour,

Je suis tout a fait d'accord avec votre définition de complexité mémoire et temps. Ceci dit il est bien d'étudier la complexité d'un point de vue théorique mais également pratique. Il est clair que je ne viens pas chercher sur ce forum de l'aide theorique mais bien pour m'aider a a calculer la complexité pour des données expérimentales. Je suis en Master deuxieme année recherche mathématiques et c'est comme cela que mes profs souhaitent qu'on aborde l'informatique.
Maintenant mes motivations développées pourriez-vous m'aider a trouver un moyen en C d'étudier la complexité mémoire expérimentale.


Je vous remercie par avance de vos interventions qui nous ferons avancées.

[Emmanuel Delahaye]

Je suis en Master deuxieme année recherche mathématiques

Ca en jette...

Je vous remercie par avance de vos interventions qui nous ferons avancées.

Et tu as passé le BAC avec une orthographe comme ça ?

[Thierry Chappuis]

bonjour,

Je suis tout a fait d'accord avec votre définition de complexité mémoire et temps. Ceci dit il est bien d'étudier la complexité d'un point de vue théorique mais également pratique. Il est clair que je ne viens pas chercher sur ce forum de l'aide theorique mais bien pour m'aider a a calculer la complexité pour des données expérimentales. Je suis en Master deuxieme année recherche mathématiques et c'est comme cela que mes profs souhaitent qu'on aborde l'informatique.
Maintenant mes motivations développées pourriez-vous m'aider a trouver un moyen en C d'étudier la complexité mémoire expérimentale.


Je vous remercie par avance de vos interventions qui nous ferons avancées.

Le problème de la mesure, c'est qu'elle est trop influencée par des détails d'implantation et d'environnement pour tirer de réelles conclusions généralement applicables (indépendante de l'architecture matérielle, du système, etc.) au sujet de algorithme étudié. Lorsqu'on mesure le temps d'exécution d'une fonction dans un environnement multitâches, par exemple, il faut tenir compte du surcoût engendré par l'exécution pseudo-parallèle de plusieurs processus et des changements de contexte qui en résulte. Idem pour la compexité mémoire. Prenons le code suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
 
struct MaStruct_1 {
    char a;
    int m;
    char b;
    int n;
    char c;
    int o;
    char d;
    int p;
};
 
struct MaStruct_2 {
    int m;
    int n;
    int o;
    int p;
    char a;
    char b;
    char c;
    char d;
};
 
int main(void)
{
    printf("La taille de MaStruct_1 est %u\n", (unsigned) sizeof (struct MaStruct_1));
    printf("La taille de MaStruct_2 est %u\n", (unsigned) sizeof (struct MaStruct_2));
 
    return 0;
}

Les structures MaStruct_1 et MaStruct_2 sont équivalentes du point de vue de l'abstraction qu'elles représentent (si on peut parler d'abstraction ici). Mais les contraintes d'alignements font que, sur ma machine, elles occupent une place en mémoire qui varie de façon substantielle.

Si tu mesures la complexité mémoire (ou de temps) d'un algorithme codé avec les pieds, je doutes que tu puisses en tirer une quelconque conclusion quant à son efficacité intrinsèque et utiliser ces résultats pour les comparer à d'autres algorithmes. Lorsqu'on désire étudier des algos trop complexes pour se prêter à une étude "théorique", l'environnement de test doit être défini avec beaucoup de soins. Il convient également de rester prudent sur les extrapolations qu'il sera possible de pourra faire à l'aide de ces mesures.

Thierry