Scribd
Importer
17 vues9 pages

Analyse de la complexité des algorithmes

Ce document contient des informations sur des algorithmes de complexité pour trouver des maximums locaux dans des matrices et listes de manière itérative et récursive. Il présente également des exemples de graphes orientés non connexes représentant des chemins de descente.

Transféré par

Ayoub EL
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
17 vues9 pages

Analyse de la complexité des algorithmes

Ce document contient des informations sur des algorithmes de complexité pour trouver des maximums locaux dans des matrices et listes de manière itérative et récursive. Il présente également des exemples de graphes orientés non connexes représentant des chemins de descente.

Transféré par

Ayoub EL
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Problème 1 :

Dans tout le problème, notons que T est de taille NxM

Préliminaires :
1)

2)

3)

4)

5)

Partie 1 :
6)

7)

8)
La complexité de la fonction pic() est O(NxM)
9)
Le principe « diviser pour régner » consiste à décomposer le problème en plusieurs
sous problèmes et de résoudre indépendamment chaque sous problème.
Par exemple, pour chercher le max d’une liste, on décompose la liste en sous liste et
on calcule le max de chaque sous liste, après on prend le max de ces max
10)

11)
Soit C(2^n) la complexité de la fonction maxi pour une liste de taille 2^n
Donc on C(2^n) = 2*C(2^(n-1)) , C(1) = O(1)
Alors C(2^n) = 2^(n-1) *C(1)
Donc, la complexité de maxi est de O(2^n)
12)

13)
Soit C(2^n) la complexité de la fonction pic2 pour une matrice de taille de taille
(2^n)* (2^n)
C(2^n) = 2*C(2^(n-1)) +O(1) , C(1)=O(1)
Donc C(2^n) = 2^(n-1) *C(1) + O(n)
Alors la complexité de pic2 est de O(2^n)=O(M)

14)
Dans l’approche itérative, on a une complexité de O(NxM), donc dans le cas où N=M
la complexité est O(M²), alors que dans l’approche récursive la complexité est de
O(M), en termes de complexité l’approche récursive est meilleure que l’approche
itérative
Partie 2 :
15)

16)

17)

18)

19)
7 8 9 53
-1 -1 20 53
-1 -1 4 4

20)
Partie 3 :
21)

22)

23)

24)
Supposons que la liste descente à n éléments, donc la complexité des deux fonctions
est O(n)
25)
Pour estDescente(L), le nombre de cases mémoire utilisés au maximum est : 9 pour
calculer les voisins de L[n-1]+ 9 pour calculer les voisins de L[0], donc 18 cases
Pour longueur(L), à chaque fois une crée un copie de la liste avec un élément de
moins jusqu’à arriver à une liste vide, donc le nombre de cases mémoire utilisés est :
0+1+2+…+(n-1) = n(n-1)/2
La fonction récursive est gourmande en mémoire par rapport à celle itérative
26)

27)
Le graphe sera orienté indiquant la direction du chemin de la descente, ainsi qu’il
peut être non connexe car il se peut que deux points de départ aient des descentes qui
n’ont pas d’intersection
28)

29) (voir Djikstra)


Problème 2

Vous aimerez peut-être aussi