Discussion :

[l1informatique]

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

[foetus]

Analyse de la complexité des algorithmes

[l1informatique]

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

[foetus]

mais ce qui me bloque c'est comment utiliser ça ??

Simple

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

[l1informatique]

Simple

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

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

[picodev]

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

Bonjour,
je ne comprends rien car la référence que tu donnes est ce tableau que tu aurais dû fournir →


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

[sambia39]

Bonjour

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

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.

[l1informatique]

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

[picodev]

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

Code :

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

1
2
3
4
5
6
procédure insérer( tableau, position, valeur)
début
  pour i de position à tableau.longueur faire
    tableau[i+1]=tableau[i]
  tableau[position]=valeur
fin.

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