Cours et notion d’algorithme et de complexité, tutoriel & guide de travaux pratiques en pdf.

Opération fondamentale

Structures de données Christian Carrez Cnam Algorithmes et complexité 4  peut être complexe, mais de durée indépendante des données si plusieurs opérations fondamentales, décompte séparé, et coefficient opération de détail prises en compte par absorption comparaison entre algorithmes si mêmes opérations exemples:
¨ addition des distances dans voyageur de commerce
¨ comparaison de valeurs dans une recherche ou un tri
¨ déplacements de valeurs dans un tri
¨ accès à la mémoire secondaire

Calcul de la complexité

Structures de données Christian Carrez Cnam Algorithmes et complexité 5  évaluer le nombre d’exécutions de l’opération fondamentale var T: tableau [1..N] de T_Elem; {rangé par valeurs croissantes}
k : entier;
début k := 1; tant que k <= N et alors T[k] < x faire k := k+1; fait;
retourner k;
fin
invariant: pour tout j < k, t[j] < x
sortie de boucle: k = N+1 ou (k£N et T[k]³x)
complexité: au mieux 1, au pire N, en moyenne N/2
{1, ou 2, ou 3,…, N} si kN et N si k=N+1

Définitions

Structures de données Christian Carrez Cnam Algorithmes et complexité 6  Soit Dn l’ensemble des données de taille n et coût A (d) le coût de l’algorithme sur la donnée d complexité au mieux MinA(n)=min{coût A(d) | d Dn } complexité au pire MaxA(n)=max{coût A(d) | d Dn } complexité en moyenne MoyA(n)={p(d)*coût A(d) | d Dn}
où p(d) est la probabilité d’avoir le donnée d
MinA(n)  MoyA(n)  MaxA(n)

Ordre de grandeur

Structures de données Christian Carrez Cnam Algorithmes et complexité 8  l’important est l’ordre de grandeur, et l’évolution en fonction de la taille
définition: f est dominée par g, f = O(g) s’il existe n0 et c tels que pour tout n > n0, on ait f(n)  c g(n)
définition: f et g sont du même ordre de grandeur, f = (g)
s’il existe n0 , c1 et c2 tels que
pour tout n > n0, on ait c1 g(n)  f(n)  c2 g(n)