pc 2 : tri et recherche 1

PC 2

Algorithmes de tri et de recherche

• Complexité des algorithmes

• Algorithmes de tri

• Algorithmes de recherche – Recherche séquentielle

– Recherche dichotomique

– Hachage

Complexité des algorithmes

Donnée de taille n

• Temps de calcul T (n)

• Espace mémoire utilisé E(n) Evaluation:

• En moyenne

• Au pire des cas Calcul à une constante multiplicative près: pas d’unité de temps ou d’espace.

Pour deux fonctions réelles positives f et g, on écrit

f = O(g)

si f ne croit pas plus vite que g :

∃C, N ≥ 0, ∀n ≥ N, f(n) ≤ Cg(n) On écrit aussi

f = Ω(g) pour g = O(f)

et f = Θ(g) pour f = O(g) et g = O(f).

Algorithmes de tri

Donnée : N nombres entiers

a[0], a[1], …, a[N − 1]

Résultat : Réarrangement croissant b[0], b[1], …, b[N − 1] des nombres a[i].

Autre formulation : Recherche de la permutation π de {0, 1, …, N − 1} telle que

a[π[i]] = b[i]

L’entier π(i) est la place dans a du i-ème élément de b. Exemple:

a = 24 5 81 2 45
b = 2 5 24 45 81
π = 4 2 1 5 3

Complexité : O(n^{2}) pour les schémas simples et O(n log n) pour les plus élaborés.

Tri par insertion

Principe: A la i-ème étape, insérer a[i] parmi a[0], a[1], …, a[i − 1].

static void triInsertion() {
  int i,j,v;
  for (i=1; i< N; ++i) {
    v = a[i]; j = i;
    while (j>0 && a[j-1] > v) {
      a[j] = a[j-1];
      --j;
    }
    a[j] = v;
  }
}

Temps de calcul: Θ(n^{2}) au pire des cas et en moyenne.

Programme complet

class TriInsertion {
final static int N = 10;
static int[] a = new int[N];
static void initialisation() {
  for (int i= 0; i< N; i++)
    a[i] = (int) (Math.random() * 128);
}
static void impression() {
  for (int i= 0; i< N; i++)
    System.out.print(a[i]+ " ");
    System.out.println();
}
static void triInsertion() {...}
public static void main(String[] args) {
  initialisation();
  impression();
  triInsertion();
  impression();
}
}

Tri de la bulle

Principe: Faire venir en a[i] l’élément minimum de a[i], a[i + 1], …, a[N − 1] par échange d’éléments adjacents (les éléments légers montent).

5 2 1 3 4 1 5 2 3 4 1 2 5 3 4 1 2 3 5 4 1 2 3 4 5

static void triBulle() {
  int i, j, t;
  for (i= 0; i< N; ++i)
    for (j= N-1; j> i; --j)
      if (a[j-1] > a[j]) {
        t= a[j-1]; a[j-1]= a[j]; a[j]= t;
      }
}

Complexité: Θ(n^{2}) au pire des cas et en moyenne.

Analyse en moyenne

On raisonne sur la permutation π donnant la place du i-ème élément. Une inversion de π est une paire (i, j) d’indices telle que i < j et π[i] > π[j]. Chaque échange de deux éléments de a par l’algorithme supprime exactement une inversion de π. Le nombre d’échanges est donc égal au nombre d’inversions de π.

Or le nombre moyen d’inversions d’une permutation^{1} est

\frac{N(N − 1)}{4}

d’où une complexité moyenne en Θ(N^{2})

1le nombre total d’inversions de π et de la permutation π̃ image miroir de π est N(N − 1)/2

pc 2 : tri et recherche 8

Algorithmes de recherche

But : consultation et mise à jour d’un ensemble de données avec les fonctions de

• Recherche

• Insertion

• Suppression On s’intéresse à des ensembles de N éléments avec N éventuellement très grand (N ≈ 1Gigabit)

Recherche séquentielle

Recherche d’un entier v dans la table

a[0], a[1], …, a[N − 1]

static int Recherche(int v) {
  for (int i=0; i < N; i++)
    if (v == a[i]) return i;
  return -1;
}

Complexité: Θ(N) (avec N/2 opérations en moyenne).

En pratique: environ 1mn pour 1 Giga éléments (si on fait 10^{7} comparaisons/s).

Recherche dichotomique

Hypothèse: La table est ordonnée:

a[0] < a[1] < … < a[N − 1]

static int Dicho (int v) {
  int i, g, d;
  g= 0; d= N-1;
  while (g <= d) {
    i=(g+d)/2;
    if (v == a[i]) return i;
    if (v < a[i]) d= i-1;
    else g= i+1;
  }
  return -1;
}

Complexité: Θ(log N). Pour N = 10^{4}, on a 14 comparaisons environ au lieu de 5000 pour la recherche séquentielle.

pc 2 : tri et recherche 11

Dichotomies

Si, pour n ≥ 1

T (n) ≤ T (n/2) + a

alors

T (n) = O(log n)

Démonstration : il suffit de vérifier par récurrence sur n que

T (n) ≤ a log n + b

avec b = T (0).

Hachage

Principe: on utilise une fonction

h : E → [0..N − 1]

telle que a[h(x)] = x. La recherche devient immédiate.

Figure 1:

Problèmes:

• Choix de la fonction de hachage. Par exemple,

h(x) = x mod N

• Gestion des collisions: x ≠ x′ avec h(x) = h(x′). Deux solutions:

1. hachage ouvert: on gère des listes d’éléments de même clé.

2. hachage fermé: on utilise des valeurs de remplacement.

Hachage fermé

Principe: On utilise une suite de fonctions de hachage h_{1}(x), h_{2}(x), … pour ranger x. Par exemple:

h_{i}(x) = h(x) + i mod N

(hachage linéaire) ou encore

h_{i}(k) = h(k) + ih′(k) mod N

(hachage double).

On choisit h′ de façon que N et h′(k) soient toujours premiers entre eux (par exemple N est une puissance de 2 et h′(k) est impair).

Programmes pour la recherche et l’insertion avec un hachage linéaire :

Recherche d’un élément :

static int Recherche (int x) {
int i;
i= h(x);
while (a[i] != VIDE) {
  if (a[i] == x) return i;
  i= (i+1) % N;
}
return -1;
}

Insertion d’un élément :

static int Inserer(int x) {
int i;
i= h(x);
while (a[i] != VIDE && x != a[i])
   i= (i+1) % N;
a[i] = x;
return i;
}

Analyse en moyenne du hachage fermé

Hypothèse: Le rehachage est uniforme: Les valeurs h_{1}(x), h_{2}(x), … sont successivement indépendantes et ont chacune une distribution uniforme.

Taux de remplissage: α = card(E)/N.

Figure 2: pc 2 : tri et recherche 16

Nombre moyen d’essais pour insérer un élément:

1 + α + α^{2} + … = \frac{1}{1 − α}