Cours ASD

for i in range(n): # Fait n itérations
    ...

for i in range(n): # Fait n itérations
    for j in range(n): # Fait n itérations
       ...

La première boucle fait \(n\) itérations, et la seconde fait \(n\) fois \(n\) itérations, soit \(n^2\) itérations

Compter les itérations dans des algos classiques

Recherche d'un élément dans un tableau de taille \(n\)

  • Recherche linéaire
    for i in range(n):
    if t[i] == valeur:
        return i

    On a donc, au maximum : \(\sum_{i = 0}^{n - 1}{1} = n\) au maximum, car la boucle peut s'arrêter avant. Au minimum, il y a une itération, quand la première valeur recherchée est en première position.

    Quand on compte le nombre d'itérations/ l'espace mémoire, on peut avoir à distinguer le meilleur cas et le pire cas. Quand le meilleur et le pire des cas sont assez différent, il faut si possible caractériser le cas moyen.

    Pour la recherche d'une valeur dans un tableau, en moyenne, si la valeur existe dans le tableau, on fera \(\frac{n}{2}\) itérations. On suppose que la valeur cherchée à la même probabilité d'être dans chacune des cases. Nombre d'itérations moyen:

    \begin{align*} &1 \times \frac{1}{n} + 2 \times \frac{1}{n} + \dots + n \times \frac{1}{n} \\ &= \frac{1}{n} \left(1+2+\dots +n \right) = \frac{1}{n} \frac{n\left(n+1\right) }{2} = \boxed{\frac{n+1}{2}} \end{align*}
  • Recherche dichotomique
    while debut <= fin and not found:
    pos = (debut + fin)//2
    if t[pos]...
    # Mettre à jour début, fin ou trouvé

    Combien d'itérations dans le pire des cas ?

    On part d'un tableau de taille \(n\) qu'on divise en 2 à chaque itération, donc le nombre d'itérations est \(\log_{2}\left(n\right) +1\)

Comportement asymptotique des algos

On va regarder le nombre d'itérations, l'espace mémoire par rapport à des fonctions connues, comme par exemple \( n, n^2, \log n, 2^{n} \), ou plus généralement, \( n^{k} \log ^{k ^{\prime}} p^{n} \) avec \( k, k ^{\prime} \in \mathbb{R} , p \in \mathbb{N} \) . On parle de complexité en temps et en mémoire. On veut comparer l'évolution du nombre d'itérations (ou de l'espace) par rapport à ces fonctions. On utilise des notations (De Landau) : \( O, \Theta, \Omega \).

Simplifications/égalités connues

  • \( f(n) = \Theta (f(n)) \)
  • \( f(n) = \Theta (g(n)) \iff g(n) = \Theta (f(n)) \)
  • \( f(n) + g(n) = \Theta (\max (f(n) , g(n))) \)
  • \( f_1 = \Theta (g_1) \land f_2 = \Theta (g_2) \iff f_1 \times f_2 = \Theta (g_1 \times g_2) \)

Complexités des opérations sur les listes et tableaux

  Tableau Liste chaînée
Accès tête \( \Theta (1) \) \( \Theta (1) \)
Accès queue \( \Theta (1) \) \( \Theta (n) / \Theta (1) \)
Accès ième \( \Theta (1) \) \( O(n) \)
Ajout en tête \( \Theta (n) \) \( \Theta (1) \)
Ajout à la fin \( \Theta (1) \) \( \Theta n \)
Supprimer fin \( \Theta (1) \) \( \Theta (n) \)
Insertion à une pos donnée \( O(n) \) \( \Theta (1) \)
Recherche \( O(n) \) \( O(n) \)

Les dictionnaires

Type de données abstrait

Un type de données abstrait associant une clé et une valeur

  • Créer un dictionnaire vide
  • Associer une valeur à une clé
  • Accès à une valeur associée à une clé
  • Suppression de la clé et sa valeur associée
  • Existance d'une clé

Une structure de données possible pour le TDA dictionnaire est une liste de tuples. Cependant, cette implémentation est assez limitée : pour savoir si une clé est dans le dictionnaire, il faut faire un parcours de la liste. Heureusement, on a une solution.

Il faut utiliser une fonction de hachage, qui est une fonction déterministe qui associe à tout élement (non mutable) un entier. Soit un tableau de taille \( n \) et une fonction de hachage \( f \). La position d'insertion de \( x \) dans la table est déterminée par \( f(x) \mod n \)

\[ \exists x_1 \neq x_2 \text{ tel que } h(x_1) = h(x_2). \]

La fonction n'est pas injective ! Quand deux élements différents sont hachés à la même position, on parle de collision

Prenons \( f(x) \) pour \( x \in \mathbb{N} \) qui consiste à faire la somme des chiffres de \( x \). Prenons \( n = 10 \)

  1. On insère \( (43, a) \)
    • \( f(43) = 7 \mod 10 = 7 \) -> On insère en position 7
  2. Insertion de \( (97, c) \)
    • \( f(97) = 16 \mod 10 = 6 \) -> On insère en position 6
  3. Insertion de \( (413, z) \)
    • \( f(413) = 8 \mod 10 = 0 \) -> On insère en position 8
  4. La clé 217 a t-elle été insérée ?
    • \( f(217) = 10 \mod 10 = 0 \) -> La case 0 est vide, donc ok :D
  5. Insertion de \( (89, e) \)
    • \( h(89) = 17 \mod 10 = 7 \) -> On est triste :( il y a une collision :((( Comment régler ça ?

Gestion des collisions

  • Première solution : Chercher la première place libre selon une stratégie donnée (sondage) -> table à adressage ouvert
  • Deuxième solution : Avoir une liste chaînée à chaque case du tableau et insérer chaque couple (clé, valeur) en tête de liste -> table à adressage fermée

Stratégie de sondage

\( h(k, i) \) est la fonction de hachage pour la ième tentative avec la clé \( k \) tel que \( (h(k, 1) = h(k)) \)

  • Sondage linéaire \[ h(k, i) = \left(h(k) + a \times i \right) \mod n \] Avec une constante \( a \in \mathbb{N} ^{*} \). Il faut faire en sorte que \( a \) et \( n \) soient premiers entre eux. Lors de la recherche d'une place libre ou d'une clé existante, le sondage s'arrête lors de la première place libre trouvée.

    La clé \( 321 \) a été insérée ? Avec \( h(k, i) = (h(k) + i) \mod n \)

    On itère sur les \( i \) jusqu'à trouver une case vide (ou non).

    Lors de la suppression, il faut mettre la case dans un état particulier "supprimée" considérée comme vide pour une insertion, mais occupée pour le sondage.

    \( n \) est le nombre de cases, et \( m \) est le nombre d'éléments insérés et \( \tau = \frac{m}{n} \)

      TAF TAO
    Ajout \( \Theta \left(1\right) \) \( O(\frac{1}{1-t}) \)
    Accès \( \Theta (\tau) \) \( O(\frac{1}{1-\tau }) \)
    Espace \( \Theta (\max (n, m)) \) \( \Theta (n) \)

    \( n \) fonction de hachage uniforme : proba de \( \frac{1}{n} \) que \( n(x) = i,, \forall i \in [0, n-1 ] \)

    Pour une TAF : Quelle est la probabilité d'une collision ? Quelle est la longueur moyenne d'une liste ? C'est \( \tau = \frac{m}{n} \)

    L'accès est donc en \( \Theta \left(\tau \right) \)

    Pour une TAO :

      Proba
    \( \geq 1 \) 1
    \( \geq 2 \) \( \frac{m}{n} \)
    \( \geq 3 \) \( \tau ^2 \)
    \( = n \) \( \tau ^{n-1} \)
       

Nombre moyen d'accès dans une TAO pour un élément :

\[ \sum_{i = 0}^{n -1 }{\tau ^{i} } = \frac{1- \tau ^{n} }{1-\tau } \leq \frac{1}{1-\tau } \]

Le hachage du coucou

On dispose de deux fonctions de hachage \( h_1, h_2 \) et de deux tables \( T_1, T_2 \) de taille \( \frac{n}{2} \) chacune. On utilise \( h_1 \) pour les accès et insertions dans \( T_1 \) et \( h_2 \) pour \( T_{2} \). Pour insérer le couple clé, valeur \( \left(k, v\right) \) , on fait :

\[ T_1[h_1(k)] = (k, v) \]

Mais si on a un couple clé, valeur \( k^{^{\prime}}, v^{^{\prime}} \) qui était déjà dans \( T_1(h_1(k^{^{\prime}} )) \), alors on stocke \( k^{^{\prime}} , v^{^{\prime}} \) dans \( T_2 \)

S'il y a encore une collision avec \( (k_3, v_3) \), on stocke ceux là dans \( T_1 \) et ainsi de suite. L'intêret est que cela permet d'avoir des temps d'accès en \( \Theta(1) \)

Algorithmes récursifs

Quicksort

Voir le fonctionnment de cet algo

Le pire des cas est quand le tableau est trié, et le meilleur cas est quand chaque pivot est la médiane du sous tableau

Soit \( q_{m}(n), q_{p}(n) \) le nombre d'itérations dans le meilleur et pire cas. On a donc, pour un tableau de taille \( n \) :

\begin{align*} q_p(n) &= n + q_p(n-1) + q_p(0) \\[10pt] q_m(n) &= n + q_m\left(\frac{n}{2}\right) + q_m\left(\frac{n}{2}-1\right) \end{align*}

Équation de récurrence

Équation linéaire

\[ c(n) = a \times c(n-1) + f(n) \]

avec \( a \) le nombre d'appels récursifs et \( f(n) \) le nombre d'itérations de cet appel

Formule générale :

\[ a^{n} \times c(0) + \sum_{i=0}^{n-1}{a^{i} \times f(n-i)} \]

si on a \( c(n-i) \), on pose \( N = \frac{n}{i} \) et \( c ^{\prime} (N) = c\left(iN\right) \)

Pour la retrouver, dérouler l'arbre des appels, les compter en fonction de a et f, et faire la somme de tous les "étages"

Équation de partition

\[ c(n) = a \times c\left(\frac{n}{i}\right) + f(n) \]

Formule générale :

Prenons \( f(n) = F \)

On a donc :

\begin{align*} &a^{p+1} \times c(0) + \sum_{i=0}^{p}{a^{i} \times F} \\[10pt] =\ &a^{\log_{i}(n) + 1} \times c(0) + F \times \frac{a^{\log_{i}+1} - 1}{a - 1} \end{align*}

Cas sans hypothèse sur f(n)

Le théorème central général permet de résoudre ces cas. Il distingue rrois cas selon le comportement asymptotique de \( f(n) \) par rapport à \( \log _{i}(a) \)

  1. \( f(n) = O\left(n^{\log _{i}(a) - \epsilon }\right) \forall \epsilon > 0 \implies c(n) = \Theta (n^{\log _{i}(a)}) \)
  2. \( f(n) = \Theta (n^{\log _{i}(a)}) \implies c(n) = \Theta (n^{\log _{i}(a)}\log (n)) \)
  3. \( f(n) = \Omega (n^{\log _{i}(a) + \epsilon }) \forall \epsilon > 0 \implies c(n) = \Theta (f(n)) \)

Created: 2026-03-05 jeu. 11:26

Validate