Cours 5 - La complexité

name: inverse
layout: true
class: center, middle, inverse

---
# Inès de Courchelle
## La complexité
## 2023 - 2024

![image](../img/CY-tech.png)

---
layout: false

# Rappel - la compilation séparée
.pull-left[
#### mesFonctions.h
```c
#ifndef __mesFonctions_H_
#define __mesFonctions_H_
...
#endif
```
#### mesFonction.c
```c
#include "mesFonctions.h"
...
```
#### main.c
```c
#include <stdio.h>
#include "mesFonctions.h"

int main(int argc,char** argv){
...
}
```
]

.pull-right[
 
<center>
 <img src="img/fonctions.svg" width=200/>
</center>

- On peut avoir plusieurs fichiers de compilation séparée
- 1 .h = 1.c
- Attention aux inclusions multiples !
- Compilation + exécution en plusieurs étapes
]
---
# Rappel - La récursivité
## Étapes
1. La condition d'arrêt
2. La résolution du problème
3. L'appel récursif

## Principes
- Une fonction qui s'appelle elle même jusqu'à atteindre une condition d'arrêt
- Le résultat de chaque fonction enfant est retourné dans les fonctions parents, jusqu’à retourner à la fonction originale

---
# Rappel - La récursivité
## Terminale
```
FONCTION exempleT(n : entier) : entier
DEBUT
    SI condition d'arret FAIRE
        RETOURNER ...
    SINON
        RETOURNER exempleT(n-1)
FIN
```

## Non terminale
```
FONCTION exempleT(n : entier) : entier
DEBUT
    SI condition d'arret FAIRE
        RETOURNER ...
    SINON
        RETOURNER n+ exempleT(n-1)
FIN
```

---
# La complexité
## Définition
.otro-blockquote[Étudier la quantité de ressource nécessaire à l'exécution d'un algorithme]
<center>
 <img src="img/lol.gif" width=250/>
</center>
.pull-left[
#### Mais pourquoi on fait ça ?
Pour trouver un bon algorithme
]
.pull-right[
#### Mais Comment ?
Avec du bon sens
]

---
# La complexité
## Objectifs
- Comparer et mesurer les performances d'algorithmes répondant à un même problème
- Réduire le temps d'exécution d'algorithme
- Utiliser au minimun la mémoire

.pull-left[
.under[Un bon algorithme doit : ]
- répondre à un problème posé
- être rapide
- consommer peu de ressource
]
.pull-right[
 
<center>
 <img src="img/lol2.jpg" width=200/>
</center>

]

.otro-blockquote[Vous savez, moi je ne crois pas qu'il y ait de bonne ou de mauvaise situation.]

---
# La complexité
## Problématique
- .under[complexité temporelle]
  - Réduire le temps d'exécution
  - Augmenter l'utilisation de la mémoire
- .under[complexité spatiale]
  - Réduire l'utilisation de la mémoire
  - Augmenter le temps d'exécution

.pull-left[
<center>
 <img src="img/complexite.svg" width=250/>
</center>
]

.pull-right[
<center>
 <img src="https://media.giphy.com/media/gF5xLnIVPTs62OfVTJ/giphy.gif" width=250/>
</center>
]

---
# La complexité
## Illustration
.pull-left[
#### Algo 1
```c
a <- 1
POUR i allant de 1 à 2000 FAIRE
 a <- a * b
FIN POUR
```
]
.pull-right[
#### Algo 2
```c
a <- 1
b2 <- b * b
POUR i allant de 1 à 1000 FAIRE
 a <- a * b2
FIN POUR
```
]

#### Quel est le meilleur algorithme ?

---
# La complexité
## Les différents types de complexité
1. La complexité en nombre de comparaisons
2. La complexité en nombre d'opérations
3. La complexité en nombre d'affectations

---
# Les comparaisons
## Définition
- C'est le nombre de comparaisons réalisées dans un algorithme
- En C, une comparaison est donnée par les opérateurs de comparaison suivant : ==, <,>, !=, <=, >=

## Cas particuliers
- Une instruction de boucle est égale à N+1-i comparaisons pour chaque variable d'itération i
- Une condition est égale à une comparaison

---
# Les comparaisons
## Illustration ALGO
.pull-left[
#### Exemple 1
```c
N <- 10
POUR i allant de 0 à N FAIRE
 ...
FIN POUR
```

N + 1 - i = 10 + 1 - 0 = 11 comparaisons

#### Exemple 2
```c
N <- 10
i<- 0
TANT QUE (i<N) FAIRE
 i <- i++
FIN TANT QUE
```

N + 1 - i = 10 + 1 - 0 = 11 comparaisons

]
.pull-right[
#### Exemple 3
```c
SI (a<10) ALORS
 ...
FIN SI
```

1 comparaison

#### Exemple 4
```c
SI (a=2 ET b=4) ALORS
    ...
FIN SI
```

2 comparaisons

]

---
# Les comparaisons
## Illustration EN C
.pull-left[
#### Exemple 1
```c
N=10;
for(int i=0;i<N;i++){}
```

N + 1 - i = 10 + 1 - 0 = 11 comparaisons

#### Exemple 2
```c
N=10;i=0;
while(i<N){i++}
```

N + 1 - i = 10 + 1 - 0 = 11 comparaisons

]
.pull-right[
#### Exemple 3
```c
if (a<10){}
```

1 comparaison

#### Exemple 4
```c
if (a==2 && b==4){}
```

2 comparaisons

]

---
# Les opérations
## Définition
- C'est le nombre de calcul réalisé dans un algorithme
- En C, une opération est donnée par les opérateurs suivant : +, -, ++,--,*, /

## Cas particulier
Une instruction de boucle *for* réalise N-i opérations pour chaque variable d'itération i.

---
# Les opérations
## Illustration
.pull-left[
#### Exemple 1 : ALGO
```c
N <- 10
POUR i allant de 0 à N FAIRE
 ...
FIN POUR
```
]

.pull-right[
#### Exemple 1 : EN C
```c
N =10;
for (i=0; i<N; i++){}
```
]

.under[Explications :]

- N - i = 10 - 0 = 10 opérations
- à chaque tour de boucle on va réaliser l'opération i <- i + 1

.pull-left[
#### Exemple 2 : ALGO
```c
N <- 10
POUR i allant de 4 à N FAIRE
 ...
FIN POUR
```
]

.pull-right[
#### Exemple 2 : EN C
```c
for (i=4; i<10; i++){}
```

]

.under[Explications :]

- N - i = 10 - 4 = 6 opérations
- à chaque tour de boucle on va réaliser l'opération i + 1

---
# Les affectations
## Définition
- C'est le nombre d'écriture réalisée dans la mémoire.
- En C, une affectation est donnée par l'unique opérateur suivant : =

## Cas particulier
Une instruction de boucle *for* réalise N+1-i pour chaque variable d'itération i

---
# Les affectations
## Illustration
.pull-left[
#### Exemple 1 : ALGO
```c
N <- 10
POUR i allant de 0 à 10 FAIRE
 ...
FIN POUR
```
]

.pull-right[
#### Exemple 1 : EN C
```c
N = 10;
for (i=0; i<N; i++){}
```
]

.under[Explications : ]

- N + 1 - i = 10 + 1 - 0 = 11 affectations
- à chaque tour de boucle i va prendre une nouvelle valeur i <- i + 1

.pull-left[
#### Exemple 1 : ALGO
```c
N <-10
POUR i allant de 4 à 10 FAIRE
 ...
FIN POUR
```
]

.pull-right[
#### Exemple 2 : EN C
```c
for (i=4; i<10; i++){}
```
]

.under[Explications : ]

- N + 1 - i = 10 + 1 - 4 = 7 affectations
- à chaque tour de boucle i va prendre une nouvelle valeur i <- i + 1

---
# Exercices
## Exercice 1
Quelle est la complexité de cet algorithme en nombre d'additions et de divisions en fonction de N ?
```c
res <- 0
POUR i allant de 0 à N FAIRE
 POUR J allant de i à i+2 FAIRE
 res <- res + 1/(i+j)
 FIN POUR
FIN POUR
```
#### Astuce :
- On peut partir d'un exemple pour n avec une valeur concréte.
- Par exemple, que se passe t-il si N= 2 ?

---
# Exercice 1
## La solution
.pull-left[
```c
res <- 0
POUR i allant de 0 à N FAIRE
 POUR J allant de i à i+2 FAIRE
 res <- res + 1/(i+j)
 FIN POUR
FIN POUR
```
 
#### Généralisation :
- .under[Boucle 1]: on l'a fait n fois
- .under[Boucle 1]: il y a n-i opération dans une boucle for (n-0)
- .under[Boucle 2]: on a 9 additions à chaque fois
- .underV[Total Additions]: 9n + (n-0);
- .under[Boucle 1] : on l'a fait n fois
- .under[Boucle 2] : on a 2 divisions à chaque fois
- .underV[Total Divisions] : 2n
]
.pull-right[
#### Pour n=2 :
<center>
 <img src="img/exo1cours.svg" width=350/>
</center>
]

---
# Exercices
## Exercice 2
Quelle est la complexité de cet algorithme en nombre d'affectations, de comparaisons et d'opérations en fonction de N ?
```c
FONCTION fact(n:entier) : entier
DEBUT
 SI (n =1) ALORS
 retourner 1
 SINON
 retourner n* fact (n-1)
 FIN SI
FIN
```
---
# Exercice 2
## La solution
```c
FONCTION fact(n:entier) : entier
DEBUT
 SI (n =1) ALORS
 retourner 1
 SINON
 retourner n* fact (n-1)
 FIN SI
FIN
```
.under[Affectation]
- Il y a une affectation dans l'appel de la fonction
- Si n=1 alors il y a 1 affectation. Soit A(1)=1
- Si n=2 alors A(2)=1+A(1)
- Si n=3 alors A(3)=1+A(2) <=> 1 + [1 + A(1)]
- Si n=4 alors A(4)=1+A(3) <=> 1 + [1 + A(2)] <=> 1 + [1 + [1 + A(1)]]
- Si n>1 alors A(n) = 1+A(n-1) = 1+1+A(n-2)

---
# Exercice 2
## La solution
```c
FONCTION fact(n:entier) : entier
DEBUT
    SI (n =1) ALORS
        retourner 1
    SINON
        retourner n* fact (n-1)
    FIN SI
FIN
```
.under[Comparaisons]
- Il y a une comparaison dans if
- Si n=1 alors il y a 1 comparaison. Soit C(1)=1
- Si n>1 alors C(n)= 1+C(n-1) = .underV[1+1+C(n-2)]

.under[Opérations]
- Il y a 2 opérations la multiplication et la soustraction
- si n=1 alors il y a zéro opération !
- si il n>1, alors OP(n)= 2+OP(n-1) =.underV[2+2+OP(n-2)]

---
# La notation
- La complexité ne prend en compte qu'un ordre de grandeur
- On parle d'ordre de complexité :
  - Pour représenter cette approximation la notation est Ο
  - Pour dire qu'une méthode s'effectue environ en N², ont dit qu'elle a une complexité  Ο(N²)

Il n'est donc pas nécessaire de comptabiliser chaque opération élémentaire d'un algorithme pour avoir une idée de sa complexité.

---
# De manière générale
## Appel de fonctions
Si on regarde la complexité en terme d'appel de fonctions
.pull-left[
#### Exemple 1

\\[ 2N + 5 \\]
]
.pull-right[
 
La complexité est Ο(N);
]

.pull-left[
#### Exemple 2
\\[ N \over 2 \\]
]
.pull-right[
 
La complexité est Ο(N);
]

.pull-left[
#### Exemple 3
\\[ 2N^2 + 3N + 5 \\]
]
.pull-right[
 
La complexité est Ο(N²);
]
---
# Les classes
## Appelation
- Ο(1) : complexité constante
- Ο(n) : complexité linéaire
- Ο(n log n) : complexité quasi-linéaire
- \\[Ο(N^a)\\] : complexité polynomiale
- \\[Ο(e^n)\\] : complexité exponentielle
- ...

## En pratique
- Les algorithmes à complexité quasi-linéaire et en dessous sont très efficaces
- Sur les données réduites, les algorithmes polynomiaux sont encore applicables
- Un algorithme à complexité exponentielle est inutilisable

---
# Les classes
## Représentation
<img src="img/classe_comp.png" width=450/>

---
# Exercices
## Exercice 3
```c
FONCTION fibo (n : entier) : entier
DEBUT
 SI (n< 2) ALORS
 retourner n
 SINON
 retourner fibo(n-1) + fibo(n+2)
 FIN SI
FIN
```
Quel est la complexité en nombre d'appel de cet algorithme ?

---
# Exercice 3
## La solution

```c
FONCTION fibo (n : entier) : entier
DEBUT
 SI (n< 2) ALORS
 retourner n
 SINON
 retourner fibo(n-1) + fibo(n+2)
 FIN SI
FIN
```
.pull-left[
- Si C(0) = 1
- Si C(1) = 1
- Si C(2) = 1 + C(2-1) + C(2-2)
- ...
- Si C(n)= 1+ C(n-1)+ c(n-2)
- On obtient un arbre exponentiel
]
.pull-right[
<center>
 <img src="img/fibo.svg" width=250/>
</center>
]
---
# Les différents cas
Pour chaque Algorithme, il convient de calculer la complexité :
- Dans le pire cas
- Dans le meilleur cas
- Dans le cas moyen

---
# Le meilleur cas 1/2
.otro-blockquote[C'est la situation la plus favorable, où l'algorithme met le moins de temps à s'exécuter.]
Nous considérons un programme qui cherche dans un tableau ordonné une valeur X demandée par l'utilisateur,dans un tableau de taille N.
.pull-left[
```c
ECRIRE ("Entrez un nb :")
LIRE (X)
i <- 0
trouve <- 1
TANT QUE (i < N ET !trouve) FAIRE
 SI (monTab[i] = X) ALORS
 trouve <- 0
 FIN SI
 i <- i +1
FIN
```
]

.pull-right[

| 4 | 25 | 30 | 400 | 500 |

.under[Quel est le meilleur cas ?]
<center>
 <img src="https://media.giphy.com/media/KEXt7M5XejR3n0avU5/giphy.gif" width=250/>
</center>

]

---
# Le meilleur cas 2/2
.otro-blockquote[Ici, le meilleur cas est lorsque l'on cherche la première valeur du tableau.
L'algorithme ne fera qu'un tour de boucle, et donc, peu d'opérations/affectations/comparaisons]
.pull-left[
```c
ECRIRE ("Entrez un nb :")
LIRE (X)
i <- 0
trouve <- 1
TANT QUE (i < N ET !trouve) FAIRE
 SI (monTab[i] = X) ALORS
 trouve <- 0
 FIN SI
 i <- i +1
FIN
```
]

.pull-right[

| 4 | 25 | 30 | 400 | 500 |

Le meilleur cas est 4 !

]

---
# La complexité pire des cas 1/2
.otro-blockquote[C'est la situation la plus défavorable, où l'algorithme met le plus de temps à s'exécuter.]
Nous considérons un programme qui cherche dans un tableau ordonné une valeur X demandée par l'utilisateur,dans un tableau de taille N.
.pull-left[
```c
ECRIRE ("Entrez un nb :")
LIRE (X)
i <- 0
trouve <- 1
TANT QUE (i < N ET !trouve) FAIRE
 SI (monTab[i] = X) ALORS
 trouve <- 0
 FIN SI
 i <- i +1
FIN
```

]

.pull-right[

| 4 | 25 | 30 | 400 | 500 |

.under[Quel est le pire cas ?]

]
---
# La complexité pire des cas 2/2
.otro-blockquote[Ici, le pire cas est lorsque l'on cherche la dernière valeur du tableau ou une valeur qui n'y est pas !
L'algorithme fera N tours de boucle, et donc, plus d'opérations/affectations/comparaisons.]
.pull-left[
```c
ECRIRE ("Entrez un nb :")
LIRE (X)
i <- 0
trouve <- 1
TANT QUE (i < N ET !trouve) FAIRE
 SI (monTab[i] = X) ALORS
 trouve <- 0
 FIN SI
 i <- i +1
FIN
```
]

.pull-right[

| 4 | 25 | 30 | 400 | 500 |

Le pire cas est 500 !

<center>
 <img src="https://media.giphy.com/media/12GP2pkws57gd2/giphy.gif" width=300/>
</center>
]

---
# La complexité moyen cas 1/2

.otro-blockquote[C'est la situation moyenne, où l'algorithme met un temps moyen à s'exécuter. On suppose que les données sont réparties selon une certaines loi de probalités.]
Nous considérons un programme qui cherche dans un tableau ordonné une valeur X demandée par l'utilisateur,dans un tableau de taille N.
.pull-left[
```c
ECRIRE ("Entrez un nb :")
LIRE (X)
i <- 0
trouve <- 1
TANT QUE (i < N ET !trouve) FAIRE
 SI (monTab[i] = X) ALORS
 trouve <- 0
 FIN SI
 i <- i +1
FIN
```
]

.pull-right[

| 4 | 25 | 30 | 400 | 500 |

.under[Quel est le moyen cas?]

]

---
# La complexité moyen cas 2/2

.pull-left[
```c
ECRIRE ("Entrez un nb :")
LIRE (X)
i <- 0
trouve <- 1
TANT QUE (i < N ET !trouve) FAIRE
 SI (monTab[i] = X) ALORS
 trouve <- 0
 FIN SI
 i <- i +1
FIN
```
 
<center>
 <img src="https://media.giphy.com/media/yqtpq8rqqXBh6/giphy.gif" width=300/>
</center>
]

.pull-right[

- Considérons que l'on a 50% de chance que x soit dans le tableau, et 50% de chance qu'il n'y soit pas.
- Sa position est au milieu
- On a donc :
  - \\[ {1\over{2} }N \\] de proba que x soit dans le tableau
  - \\[ {1\over{2} }N \\] de proba que x ne soit pas dans le tableau
  - \\[ {1\over{2} }N \\] est la position du tableau
  - Au final => \\[N + {N\over{2}} \\]

]

---

# Bilan
.otro-blockquote[Deux algorithmes qui pour les mêmes données d’entrée donnent le même résultat, ne sont pas forcément équivalents.]

.pull-left[
### Moi avant le début du cours
<center>
 <img src="https://media.giphy.com/media/Wn74RUT0vjnoU98Hnt/giphy.gif" width=200/>
</center>
]

.pull-right[
### Moi Maintenant

<center>
 <img src="https://media.giphy.com/media/qxkQ5PLLCnXW0/giphy.gif" width=200/>
</center>
]