Version imprimable
Bonjour,
Quelqu'un peut m'aider pour comprendre cette question:
lisez la section OVERVIEW OF DATA STRUCTURES, table 1.1, à la p. 14 de DATA STRUCTURES AND
ALGORITHMS IN
24 HOURS77 (Robert Lafore) et caractérisez la performance des algorithmes
qui manipulent ces structures dans le pire des cas.
merci
BONJOUR,
Merci pour le lien, si j'ai bien compris comme c'est un tableau je dois utilisé
complexité quadratique (polynomiale). mais ce qui me bloque c'est comment utiliser ça ??
voici le tableau :
Employee number:
Social security number:
Last name:
First name:
Street address:
City:
State:
Zip code:
Phone number:
Date of birth:
Date of first employment:
Salary:
merci
Simple :mrgreen:Citation:
Envoyé par l1informatique
Si c'est une complexité N², donc cela veut dire que ton algo est tout lent et qu'il faut réfléchir à l'améliorer (en O(N), en O(log N) et petit frère, ou en O(1) (mais il ne faut pas trop espérer))
Citation:
Envoyé par foetus
J'essaye de comprendre :s, je sais que c'est lent :s.
pour ce tableau qui contient des 12 lignes d'information de n emplyeurs.
pour caractérisez la performance des algorithmes qui manipulent ces structures dans le pire des cas.
comme c'est un tableau de une liste d'employeur on calculera avec O(n)
Le tableau est constitué d’un nombre fini de lignes. Appelons-les 1(1) `a l(k) .
Soit n1 ... nk le nombre de fois qu’elles sont effectu ́ees. La complexit ́e de l’algo
est n(j) l’une des lignes qui est effectuée le plus souvent. Si toutes les lignes s’effectuent en
temps O(1), la complexit ́e de l’algorithme est majorée par knj O(1) soit O(nj ).
C'est ça la réponses ?
merci
Citation:
Envoyé par l1informatique
Bonjour,Citation:
Envoyé par l1informatique
je ne comprends rien car la référence que tu donnes est ce tableau que tu aurais dû fournir →
Pièce jointe 215335
Explique toi un peu mieux car je ne vois pas du tout à quoi ton deuxième message fait référence !
Sinon le tableau du livre liste des sdd avec des remarques sur l'accès, l'insertion, la suppression et la recherche.
J;imagine que les réponses attendues sont par exemple :
accès insertion suppression recherche tableau O(1) O(n) O(n) O(n) tableau trié ... ... ... ...
Bonjour
Citation:
Envoyé par l1informatique
Il y a un truc que je ne comprends pas ou j’ai dû peut-être zapper. Par quelle conclusion arrivez-vous à une complexité quadratique, je ne vois pas en quoi un simple tableau peut avoir cette complexité.
De plus, vous nous citez les noms de tableaux, mais en réalité cela correspond à des membres d’une structure. Au final, votre évaluation de complexité se base sur quoi en réalité ?
S’agit-il d’une évaluation de complexité en temps ou en nombre d’opérations ?
Personnellement, je dirais en nombre d’opérations car il s’agit de structure de donnée.
La liste des tableaux donnée par @picodev est déjà un bon point de départ, mais s’il faut aller plus loin dans ce que vous appeler « l’évaluation des structures dans le pire des cas » alors, il faut procéder autrement en utilisant par exemple une analyse dite amortie qui vous permettra d’évaluer la complexité temporelle de l’ensemble des opérations ou une opération sur votre structure de données, ce qui vous permettra de connaitre le cas le plus défavorable (pire des cas) et de savoir si elle impacte ou pas de façon globale l’ensemble des opérations sur la structure.
à bientôt.
Bonjour,
Je vous remercie pour les réponses, j'ai téléchargé un autres pdf que je croyais le bon :s.
avec ce tableau , qui ce que je dois faire au début pour commencer de caractériser la performance des algorithmes qui manipulent ces structures dans le pire des cas.
Je n'ai pas de notion dans sa. J'ai lu le cours sur la notion de complexité mais je ne vois pas comment répondre.
Merci
D'abord il faut trouver les algorithmes. Ici ce ne sont que des algos hyper classiques (en gros ceux que tout informaticien devrait connaître sur le bout des doigts). Ensuite il faut les comprendre et en calculer la complexité. Comme c'est hyper classique tu trouves une méga tonne d'info sur le net.Citation:
Envoyé par l1informatique
Par exemple l'insertion d'un élément dans un tableau → pour insérer un élément dans un tableau tu dois d'abord créer une place vide en décalant les éléments de la position d'insertion à la fin du tableau, ensuite tu insères la valeur. La complexité est mesurée en «opération élémentaires». L'algo pourrait être :
Il y a tableau.longueur-position opérations de décalages et une opération d'affectation. Donc pour un tableau donné de longueur n insérer un élément en position p «coûte» (n-p)*2+1. Ici je compte 2 pour l'opération de décalage pour un accès en lecture plus un accès en écriture, mais on pourrait compter 3,4 ou 42 ça ne changera pas beaucoup.Code:
2
3
4
5
6
Dans le pire des cas on insère en tête (p=0), et il faudra 2*n+1 opérations, c'est donc un algo en O(n).
Dans le meilleur des cas on insère en fin (p=n), et il faudra 1 opération.
En moyenne, si on suppose que p peut prendre équiprobablement n'importe quelle valeur entre 1 et n on trouve 2*(n/2)+1=n+1.
Cet algorithme a donc une complexité en moyenne et au pire des cas en O(n), sachant qu'une insertion en fin est en O(1).
Tu as beaucoup de lecture en perspective :)
Citation:
Envoyé par picodev
Woow, donc sa c'est une études pour la première collonne du tableau 1.1 (tableu), je dois faire meme choses pour tous le reste :s.
Je croyais pas que c'était aussi compliquer
Bonsoir,
Je vais essayer d’éclaircir un peu ce qui a été dit. Tout d'abord, il faut comprendre que la notion de complexité est une notion qui permet d’évaluer ce que l’on appelle le coût d’exécution d’un algorithme et ces coûts peuvent être temporels (complexité temporelle qui est une fonction de « n » qui mesure le temps de calcul pour une donnée de taille « n ») ou spatial( complexité en mémoire ou taille mémoire qui est une fonction de « n » qui mesure la place mémoire utilisée pour le calcul sur une donnée de taille « n »)
Pour mesurer un coût, il faut prendre en compte:
- La taille des données.
- Le comportement asymptotique de l’algorithme, c'est-à-dire son comportement à l’infini donc de « n »
- Le cas le plus défavorable dit «le pire des cas » (est lorsque l’on donne une borne supérieure sur le temps de calcul pour toutes les données de taille « n »), en clair, on cherche le cas où l’algorithme se déroule pendant un temps assez long (qui tend vers l’infini) et l’on dit moyenne , le temps de calculs pour toutes les données de taille « n »
Exemple:
Soit l'algorithme suivant (tiré du cours de complexité d'algorithme de Mr Laurent Moreau enseignant au CNAM): nous allons calculé la complexité de celle-ci a titre pédagogique et nous nous limiterons au comportement asymptotique.
La formule a été édité sur se site. Car il n'y pas d'éditeur de formule sur le forum
Pour calculer le temps d'exécution "t(n)" on supposera en utilisant les constante ci-dessous comme des constantes indépendantes de "n":Code:
2
3
4
5
6
7
- On note "T1" le temps d'exécution entre le début et #1
- On note "T2" le temps d'exécution de l'étape #2
- On note "T3" le temps d'exécution de l'étape #3
- On note "T4" le temps d'exécution de l'étape #4
On aura donc : Pièce jointe 215402
On définit iT le temps d'exécution d'une itération ce qui donne: Pièce jointe 215403
On obtient alors: Pièce jointe 215404 ( le temps dépend linéairement de la taille "n" (fonction affine de n) )
Le comportement asymptotique donne : Pièce jointe 215405 Conclusion l'algorithme est asymptotiquement linéaire en "n"
L'exemple ci-dessus montre comment en effectue la complexité d'un algorithme mais cela n'est pas finis il faut le cas le plus défavorable qu'il faut traité.
Corrigez-moi si je me trompe mais cette règle s'applique aux tableaux dynamiques pour lesquels on agrandit la taille pour ajouter des éléments et donc le coût d'ajout de l'élément dans le tableau en moyen est "O(1)" et le pire en "O(n)". Mais en revanche, si on prend mot pour mot votre exemple, le cas défavorable de votre exemple se présente quand la boucle atteint l'itération proche de la condition d'arrêt"tableau.longueur" (qui est la taille finie du tableau si on parle de tableaux statiques) ou pire quand en fourni une indice hors tableaux en clair, on déborde le tableau (si on parle d'implémentation d'algorithme et exécution du code on a un dépassement de tampon ou mieux le code à comportement d'une attaque buffer overflow ;) bref ).Citation:
Envoyé par picodev
Serait-il plus simple de préciser, qu'il s'agit d'un tableau dynamique ?
à bientôt
En réalité en C, il n'y a pas de tableau dynamique :mouarf: ou :aie:Citation:
Envoyé par sambia39
Tu crées un tableau A (avec malloc), ensuite tu fais un realloc, mais cela peut être le tableau A comme un nouveau tableau B.
Non, si tu veux être tatillon :mrgreen: la complexité c'est le maximum entre O(n) (pour faire l'insertion) et la complexité de realloc.
Un tableau est une variable qui peut contenir plusieurs données du même type exemple tableaux d'entier qui contient uniquement des entiers, tableaux de caractère que des caractères.Citation:
Envoyé par foetus
On comprend également que le tableau à une taille dite "dimension" ainsi on peut trouver des tableaux à deux dimensions, trois, etc.
Il existe alors:
Des tableaux dis statiques car, la taille est connue d'avance et des tableaux, dis dynamiques par le biais des variables pointeurs dont la taille est connue qu'à l'exécution..
La particularité d'un tableau statique est qu'il correspond à une allocation statique de mémoire cela signifie que l'espace mémoire est réservé en début du programme une fois pour toutes et de ce fait le tableau possède une taille fixe.
Quant au tableau dynamique l'espace mémoire est réservé et connu qu'à l'exécution ainsi donc, elle est dite dynamique et cette particularité ne peut se faire grâce au variable pointeur qui pointe sur une zone mémoire allouée par le système et mieux en peut solliciter une redimension de cette mémoire
En langage C quand on crée un tableau avec la fonction d'allocation "malloc" en alloue un bloc de taille n (et non un bloc d'un type donné) que le système d'exploitation renvoie à une variable pointeur, l'adresse du bloc alloué en cas d'erreur ou plus de mémoire la fonction renvoie NULL.
Pour redimensionner ou augmenter un tableau. On utilise la fonction "realloc()" qui a la charge de redimensionner un bloc mémoire alloué dynamiquement avec un pointeur et elle renvoie a ce pointeur l'adresse du nouveau bloc ré-alloué tout en gardant le contenu du précédent tableau. (Elle retourne NULL s'il y a échec).
Votre réponse correspond à une allocation dynamique et ma question parle de la conclusion de @picodev par rapport au notation qui traite le cas de la complexité de son exemple. En clair, son exemple est-il basé sur un tableau static ou dynamique ?Citation:
Envoyé par foetus
car, "i+1" en indice avec comme condition d'arrêt de la boucle "tableau longueur" qui est la taille du tableau, je ne peux que conclure qu'il s'agit d'un tableau static dont la taille est connue à l'avance :?
bref, pour l'instant il se fait tard. En attendant une réponse je vous souhaite une bonne nuit.
à bientôt
Impossible de le savoir :mrgreen:. On peut très bien faire XXX list[5000]; (5000 ou un nombre assez large pour nos besoins si on peut borner)Citation:
Envoyé par sambia39
Pour le reste tu as raison ;)
Bonjour,
Je suis plus perdu qu'avant, pour ma question au tout début, je ne me retrouve toujours pas.
si c'est possible de me donner une idée pour un premier exemple de tableau pour commencer.
Merci
Comme je donnais un aperçu sur le tableau 1.1 de la référence donné par le PO il s'agit évidemment d'un tableau statique (à taille fixe donc). Je ne traite pas le cas «tableau plein» car ce n'est pas important ici, on essaye de déterminer la complexité d'une fonction si elle n'échoue pas. Mais c'est vrai qu'on peut être plus exhaustif.Citation:
Envoyé par sambia39
Dans le cas d'un tableau à croissance dynamique on introduit la notion de complexité amortie. Si la croissance est exponentielle d'un facteut 𝛼>1 alors la complexité en temps amortie de l'insertion reste en O(n) malgré les réallocations qui pourraient laisser faire croire le contraire.
Je crois qu'il y a quelques imprécisions dans tout cela.Citation:
Envoyé par sambia39
En C, malloc() ne sert pas à créer des tableaux ; il alloue une bloc de mémoire et renvoie un pointeur sur le début de la zone.
La norme (n1256) donne la définition suivante au point 20 de la section 6.2.5 Types:
Un tableau est donc bien typé.Citation:
An array type describes a contiguously allocated non empty set of objects with a particular member object type, called the element type.
Array types are characterized by their element type and by the number of elements in the array.
An array type is said to be derived from its element type, and if its element type is T,the array type is sometimes called
‘‘array of T’’. The construction of an array type from an element type is called ‘ ‘array type derivation’’.
Un tableau n'est pas alloué une bonne fois pour toute à la compilation, sauf s'il est global ou statique. Sinon, il a une allocation automatique est donc normalement alloué sur la pile comme les autres variables automatiques.
C'est un abus de langage de parler de tableaux statiques et dynamiques, surtout quand le C99 introduit les VLA.
J'ai consigné des notes sur le sujet ici : https://gradot.wordpress.com/2012/08...ointeurs-en-c/
Bonsoir,
Bonne remarque, mais il y a une ambiguïté à ce que vous avez posté. Sauf erreur de ma part, je n'ai peut-être pas été clair, mais j'ai écrit:
Donc, j'entends par là que quand on utilise la fonction "malloc" pour créer un tableau, celui-ci (malloc) procède à une réservation dynamique de la mémoire, plus exactement une zone mémoire de "n" octets au moment de l'exécution du programme. De ce fait, pour allouer un vecteur de mémoire (tableau) de "n" octects de type entier, on utilisera une variable pointeur sur un type donné (entier) à laquelle on alloue une zone mémoire qui correspond "n" type [/I](entier).[I]Citation:
Envoyé par sambia39
Au final, je n'est pas dit que "malloc" servait juste à créer un tableau (sous entendus), mais qu'il sert à allouer une zone mémoire et grâce aux variables pointeur, on obtient un tableau dynamique de donnée qui est en réalité un bloc mémoire de taille "n".
Un tableau n'est rien d'autre qu'une suite de blocs de même taille. Donc, si vous créez un tableau dynamique grâce (en utilisant) à la fonction "malloc" de taille "n", vous ne faites qu'allouer "n" blocs de taille "type". (n * taille type).
J'admet que la norme aide mais il ne faut pas la prendre non plus pour "argent comptant".Citation:
Envoyé par Bktero
Le langage C, est un langage fortement typé. Il est tout à fait logique que les tableaux soient typés, d'ailleurs un tableau de type entier ne peut que contenir des élements de type entier. Pareil pour les caractères et c'est ce que j'ai mentionné dans mon précédent poste, en disant:
Citation:
Envoyé par sambia39
J'ai écris:Citation:
Envoyé par Bktero
Donc, pour le cas d'un tableau statique, exemple " int iTab[10]". iTab est un tableau de 10 éléments de type entier. 10 est une valeur constante (obligatoire). La taille du tableau "iTab" est donc défnitive (une fois pour toute) et ne peut pas être modifiée en cours d'exécution d'où j'ai écris :Citation:
Envoyé par sambia39
C99 introduit les VLA oui mais, il s'agit de tableaux à taille variable et si je devrais le classer, (personnellement) je le mettrais dans la catégorieCitation:
Envoyé par sambia39
des tableaux dite dynamique car sa taille est déterminée au moment de l'exécution.
Pour finir, sans parler de la norme C99 avec l'introduction de la VLA, je dirais qu'il n'y a pas d'abus de langage mais qu'il y a bien deux types de tableaux:
statique et dynamique et pour les raisons que j'ai énnoncé plus haut.
à bientôt
Bah si, la norme est parole d'évangile bien au contraire. Un compilateur+bibliothèque standard conforme se doit de la respecter et de documenter les comportements laissés à l'implémentation. C'est fait pour ça la norme.Citation:
Envoyé par sambia39
