---
title: "Tris et complexité"
date: "2023-11-21"
header-includes: |
    \usepackage{xcolor}
---

# Efficacité d'un algorithmique

Comment mesurer l'efficacité d'un algorithme?

. . .

* Mesurer le temps CPU,
* Mesurer le temps d'accès à la mémoire,
* Mesurer la place prise mémoire,

. . .

Dépendant du **matériel**, du **compilateur**, des **options de compilation**, etc!

## Mesure du temps CPU

```C
#include <time.h>
struct timespec tstart={0,0}, tend={0,0};
clock_gettime(CLOCK_MONOTONIC, &tstart);
// some computation
clock_gettime(CLOCK_MONOTONIC, &tend);
printf("computation about %.5f seconds\n",
       ((double)tend.tv_sec + 1e-9*tend.tv_nsec) - 
       ((double)tstart.tv_sec + 1e-9*tstart.tv_nsec));
```

# Programme simple: mesure du temps CPU

## Preuve sur un [petit exemple](../source_codes/complexity/sum.c)

```bash
source_codes/complexity$ make bench
RUN ONCE -O0
the computation took about 0.00836 seconds
RUN ONCE -O3
the computation took about 0.00203 seconds
RUN THOUSAND TIMES -O0
the computation took about 0.00363 seconds
RUN THOUSAND TIMES -O3
the computation took about 0.00046 seconds
```

Et sur votre machine les résultats seront **différents**.

. . .

## Conclusion

* Nécessité d'avoir une mesure indépendante du/de la
  matériel/compilateur/façon de mesurer/météo.

# Analyse de complexité algorithmique (1/4)

* On analyse le **temps** pris par un algorithme en fonction de la **taille de
  l'entrée**.

## Exemple: recherche d'un élément dans une liste triée de taille N

```C
int sorted_list[N];
bool in_list = is_present(N, sorted_list, elem);
```

* Plus `N` est grand, plus l'algorithme prend de temps sauf si...

. . .

* l'élément est le premier de la liste (ou à une position toujours la même).
* ce genre de cas pathologique ne rentre pas en ligne de compte.

# Analyse de complexité algorithmique (2/4)

## Recherche linéaire

```C
bool is_present(int n, int tab[], int elem) {
    for (int i = 0; i < n; ++i) {
        if (tab[i] == elem) {
            return true;
        } else if (elem < tab[i]) {
            return false;
        }
    }
    return false;
}
```

* Dans le **meilleurs des cas** il faut `1` comparaison.
* Dans le **pire des cas** (élément absent p.ex.) il faut `n` comparaisons.

. . .

La **complexité algorithmique** est proportionnelle à `N`: on double la taille
du tableau $\Rightarrow$ on double le temps pris par l'algorithme.

# Analyse de complexité algorithmique (3/4)

## Recherche dichotomique

```C
bool is_present_binary_search(int n, int tab[], int elem) {
    int left  = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = (right + left) / 2;
        if (tab[mid] < elem) {
            left = mid + 1;
        } else if (tab[mid] > elem) {
            right = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}
```

# Analyse de complexité algorithmique (4/4)

## Recherche dichotomique

![Source: [Wikipédia](https://upload.wikimedia.org/wikipedia/commons/a/aa/Binary_search_complexity.svg)](figs/Binary_search_complexity.svg){width=80%}

. . .

* Dans le **meilleurs de cas** il faut `1` comparaison.
* Dans le **pire des cas** il faut $\log_2(N)+1$ comparaisons

. . .

## Linéaire vs dichotomique

* $N$ vs $\log_2(N)$ comparaisons logiques.
* Pour $N=1000000$: `1000000` vs `21` comparaisons.

# Notation pour la complexité

## Constante de proportionnalité

* Pour la recherche linéaire ou dichotomique, on a des algorithmes qui sont $\sim N$ ou $\sim \log_2(N)$
* Qu'est-ce que cela veut dire?

. . .

* Temps de calcul est $t=C\cdot N$ (où $C$ est le temps pris pour une comparaisons sur une machine/compilateur donné)
* La complexité ne dépend pas de $C$.

## Le $\mathcal{O}$ de Leibnitz

* Pour noter la complexité d'un algorithme on utilise le symbole $\mathcal{O}$ (ou "grand Ô de").
* Les complexités les plus couramment rencontrées sont

. . .

$$
\mathcal{O}(1),\quad \mathcal{O}(\log(N)),\quad \mathcal{O}(N),\quad
\mathcal{O}(\log(N)\cdot N), \quad \mathcal{O}(N^2), \quad
\mathcal{O}(N^3).
$$

# Ordres de grandeur

\begin{table}[!h]  
\begin{center} 
\caption{Valeurs approximatives de quelques fonctions usuelles de complexité.} 
\medskip 
\begin{tabular}{|c|c|c|c|c|} 
\hline 
$\log_2(N)$ & $\sqrt{N}$      & $N$    & $N\log_2(N)$    & $N^2$     \\ 
\hline\hline 
$3$         & $3$             & $10$   & $30$            & $10^2$    \\ 
\hline 
$6$         & $10$            & $10^2$ & $6\cdot 10^2$   & $10^4$    \\ 
\hline 
$9$         & $31$            & $10^3$ & $9\cdot 10^3$   & $10^6$    \\ 
\hline 
$13$        & $10^2$          & $10^4$ & $1.3\cdot 10^5$ & $10^8$    \\ 
\hline 
$16$        & $3.1\cdot 10^2$ & $10^5$ & $1.6\cdot 10^6$ & $10^{10}$ \\ 
\hline 
$19$        & $10^3$          & $10^6$ & $1.9\cdot 10^7$ & $10^{12}$ \\ 
\hline 
\end{tabular} 
\end{center} 
\end{table} 


# Quelques exercices (1/3)

## Complexité de l'algorithme de test de primalité naïf?

```C
for (i = 2; i < sqrt(N); ++i) {
    if (N % i == 0) {
        return false;
    }
}
return true;
```

. . .

## Réponse 

$$
\mathcal{O}(\sqrt{N}).
$$

# Quelques exercices (2/3)

## Complexité de trouver le minimum d'un tableau?

```C
int min = MAX;
for (i = 0; i < N; ++i) {
    if (tab[i] < min) {
        min = tab[i];
    }
}
return min;
```

. . .

## Réponse 

$$
\mathcal{O}(N).
$$

# Quelques exercices (3/3)

## Complexité du tri par sélection?

```C
int ind = 0;
while (ind < SIZE-1) {
    min = find_min(tab[ind:SIZE]);
    swap(min, tab[ind]);
    ind += 1;
}
```

. . .

## Réponse

### `min = find_min`

$$
(N-1)+(N-2)+...+2+1=\sum_{i=1}^{N-1}i=N\cdot(N-1)/2=\mathcal{O}(N^2).
$$

## Finalement

$$
\mathcal{O}(N^2\mbox{ comparaisons}) + \mathcal{O}(N\mbox{swaps})=\mathcal{O}(N^2).
$$


# Tri à bulle (1/4)

## Algorithme

* Parcours du tableau et comparaison des éléments consécutifs:
    - Si deux éléments consécutifs ne sont pas dans l'ordre, ils sont échangés.
* On recommence depuis le début du tableau jusqu'à avoir plus d'échanges à
  faire.

## Que peut-on dire sur le dernier élément du tableau après un parcours?

. . .

* Le plus grand élément est **à la fin** du tableau.
    * Plus besoin de le traiter.
* A chaque parcours on s'arrête un élément plus tôt.

# Tri à bulle (2/4)

## Exemple

![Tri à bulles d'un tableau d'entiers](figs/tri_bulles.svg)


# Tri à bulle (3/4)

## Exercice: écrire l'algorithme (poster le résultat sur matrix)

. . .

```C
rien tri_a_bulles(entier tableau[])
    pour i de longueur(tableau)-1 à 1:
        trié = vrai
        pour j de 0 à i-1:
            si (tableau[j] > tableau[j+1])
                échanger(array[j], array[j+1])
                trié = faux
        
        si trié
            retourner
```

# Tri à bulle (4/4)

## Quelle est la complexité du tri à bulles?

. . .

* Dans le meilleurs des cas:
    * Le tableau est déjà trié: $\mathcal{O}(N)$ comparaisons.
* Dans le pire des cas, $N\cdot (N-1)/2\sim\mathcal{O}(N^2)$:
$$
\sum_{i=1}^{N-1}i\mbox{ comparaison et }3\sum_{i=1}^{N-1}i \mbox{ affectations
(swap)}\Rightarrow \mathcal{O}(N^2).
$$
* En moyenne, $\mathcal{O}(N^2)$ ($N^2/2$ comparaisons).

# L'algorithme à la main

## Exercice *sur papier*

* Trier par tri à bulles le tableau `[5, -2, 1, 3, 10, 15, 7, 4]`

```C













```

# Tri par insertion (1/3)

## But

* trier un tableau par ordre croissant

## Algorithme

Prendre un élément du tableau et le mettre à sa place parmi les éléments déjà
triés du tableau.

![Tri par insertion d'un tableau d'entiers](figs/tri_insertion.svg)

# Tri par insertion (2/3)

## Exercice: Proposer un algorithme (en C)

. . .

```C
void tri_insertion(int N, int tab[N]) {
    for (int i = 1; i < N; i++) {
        int tmp = tab[i];
        int pos = i;
        while (pos > 0 && tab[pos - 1] > tmp) {
            tab[pos] = tab[pos - 1];
            pos      = pos - 1;
        }
        tab[pos] = tmp;
    }
}
```

# Tri par insertion (3/3)

## Question: Quelle est la complexité?

. . .

* Parcours de tous les éléments ($N-1$ passages dans la boucle)
    * Placer: en moyenne $i$ comparaisons et affectations à l'étape $i$
* Moyenne: $\mathcal{O}(N^2)$

. . .

* Pire des cas, liste triée à l'envers: $\mathcal{O}(N^2)$
* Meilleurs des cas, liste déjà triée: $\mathcal{O}(N)$

# L'algorithme à la main

## Exercice *sur papier*

* Trier par insertion le tableau `[5, -2, 1, 3, 10]`

```C













```

# Complexité algorithmique du radix-sort (1/2)

## Pseudo-code

```python
rien radix_sort(entier taille, entier tab[taille]):
# initialisation
    entier val_min = valeur_min(taille, tab)
    entier val_max = valeur_max(taille, tab)
    decaler(taille, tab, val_min)
    entier nb_bits = nombre_de_bits(val_max - val_min)
# algo
    entier tab_tmp[taille]
    pour pos de 0 à nb_bits:
        alveole_0(taille, tab, tab_tmp, pos) # 0 -> taille
        alveole_1(taille, tab, tab_tmp, pos) # taille -> 0
        echanger(tab, tab_tmp)
# post-traitement
    decaler(taille, tab, -val_min)
```

# Complexité algorithmique du radix-sort (2/2)

\footnotesize

<!-- Voici une liste de parcours utilitaires de tableau:

1. Recherche de la valeur minimum ```val_min```
2. Recherche de la valeur maximum ```val_max```
3. Décalage des valeurs dans l'intervalle ```0..val_max-val_min```
4. Décalage inverse pour revenir dans l'intervalle ```val_min..val_max```
5. Copie éventuelle du tableau temporaire dans le tableau originel

On a donc un nombre de parcours fixe (4 ou 5) qui se font en $\mathcal{O}(N)$ où $N$ est la taille du tableau.

La partie du tri à proprement parler est une boucle sur le nombre de bits *b* de ```val_min..val_max```.

A chaque passage à travers la boucle, on parcourt 2 fois le tableau: la 1ère fois pour s'occuper des éléments dont le bit courant à 0; la 2ème pour ceux dont le bit courant est à 1.

A noter que le nombre d'opérations est de l'ordre de *b*  pour la lecture d'un bit et constant pour la fonction ```swap_ptr()```.

Ainsi, la complexité du tri par base est $\mathcal{O}(b\cdot N)$. -->

## Pseudo-code

```python
rien radix_sort(entier taille, entier tab[taille]):
# initialisation
    entier val_min = valeur_min(taille, tab) # O(taille)
    entier val_max = valeur_max(taille, tab) # O(taille)
    decaler(taille, tab, val_min)            # O(taille)
    entier nb_bits = 
        nombre_de_bits(val_max - val_min)    # O(nb_bits)
# algo
    entier tab_tmp[taille]
    pour pos de 0 à nb_bits:                 # O(nb_bits)
        alveole_0(taille, tab, tab_tmp, pos) # O(taille) 
        alveole_1(taille, tab, tab_tmp, pos) # O(taille)
        echanger(tab, tab_tmp)               # O(1)
# post-traitement
    decaler(taille, tab, -val_min)           # O(N)
```

. . .

* Au final: $\mathcal{O}(N\cdot (b+4))$.

# Complexité algorithmique du merge-sort (1/2)

## Pseudo-code

```python
rien tri_fusion(entier taille, entier tab[taille])
    entier tab_tmp[taille];
    entier nb_etapes = log_2(taille) + 1; 
    pour etape de 0 a nb_etapes - 1:
        entier gauche = 0;
        entier t_tranche = 2**etape;
        tant que (gauche < taille):
            fusion(
                tab[gauche..gauche+t_tranche-1], 
                tab[gauche+t_tranche..gauche+2*t_tranche-1],
                tab_tmp[gauche..gauche+2*t_tranche-1]);
            gauche += 2*t_tranche;
        echanger(tab, tab_tmp);
```

# Complexité algorithmique du merge-sort (2/2)

## Pseudo-code

```python
rien tri_fusion(entier taille, entier tab[taille])
    entier tab_tmp[taille]
    entier nb_etapes = log_2(taille) + 1
    pour etape de 0 a nb_etapes - 1: # O(log2(taille))
        entier gauche = 0;
        entier t_tranche = 2**etape
        tant que (gauche < taille): # O(taille)
            fusion(
                tab[gauche..gauche+t_tranche-1], 
                tab[gauche+t_tranche..gauche+2*t_tranche-1],
                tab_tmp[gauche..gauche+2*t_tranche-1])
            gauche += 2*t_tranche
        echanger(tab, tab_tmp)
```

. . .

* Au final: $\mathcal{O}(N\log_2(N))$.

# Complexité algorithmique du quick-sort (1/2)

## Pseudocode: quicksort

```python
rien quicksort(entier tableau[], entier ind_min, entier ind_max)
    si (longueur(tab) > 1)
        ind_pivot = partition(tableau, ind_min, ind_max)
        si (longueur(tableau[ind_min:ind_pivot-1]) != 0)
            quicksort(tableau, ind_min, pivot_ind - 1)
        si (longueur(tableau[ind_pivot+1:ind_max-1]) != 0)
            quicksort(tableau, ind_pivot + 1, ind_max)
```



# Complexité algorithmique du quick-sort (2/2)

## Quelle est la complexité du tri rapide?

. . .

* Pire des cas: $\mathcal{O}(N^2)$
    * Quand le pivot sépare toujours le tableau de façon déséquilibrée ($N-1$
      éléments d'un côté $1$ de l'autre).
    * $N$ boucles et $N$ comparaisons $\Rightarrow N^2$.
* Meilleur des cas (toujours le meilleur pivot): $\mathcal{O}(N\cdot \log_2(N))$.
    * Chaque fois le tableau est séparé en $2$ parties égales.
    * On a $\log_2(N)$ partitions, et $N$ boucles $\Rightarrow N\cdot
      \log_2(N)$.
* En moyenne: $\mathcal{O}(N\cdot \log_2(N))$.

