Correction des tds de complexité

TD1

Exercice 1

1 FONCTION min_valeurs(a,b)
2 SI a < b
3 RETOURNER a
4 SINON
5 RETOURNER b
6 FIN SI
7 FIN FONCTION

La fonction min_valeurs(a,b) est O(1) (temps constant par rapport à a et b )

1 FONCTION min_liste(tableau)
2 n <- taille(tableau)
3 min <- tableau[0]
4
5 POUR i de 0 à n - 1
6 min <- min_valeurs(min,tableau[i])
7 FIN POUR
8
9 RETOURNER min
10 FIN FONCTION

La fonction min_liste(a,b) est O(n) ou n est la taille de la liste.

Exercice 2

1 # Approche 1 : inverser le mot

2
3 FONCTION inverser_mot(mot)
4 n <- taille(mot)
5 mot_inv <- ""
6
7 POUR i de 0 à n - 1
8 mot_inv[i] <- mot[n-i-1]
9 FIN POUR
10
11 RETOURNER mot_inv
12 FIN FONCTION
13
14

inverser_mot() est O(n) ou n est la taille du mot.

1
 1 # Approche 1: vérifier si le mot et son inverse sont les mêmes
2 FONCTION est_palindrome(mot)
3 n <- taille(mot)
4 mot_inv <- inverser_mot(mot) # O(n)
5
6 POUR i de 0 de n - 1
7 SI mot[i] <> mot_inv[i]
8 RETOURNER Faux
9 FIN SI
10 FIN POUR
11
12 RETOURNER VRAI
13 FIN FONCTION

est_palindrome() est O(n). Mai elle est aussi Ω(n)

1 # Approche 2: Vérifier sur le mot

2
3 FONCTION est_palindrome_v2(mot)
4 n <- taille(mot)
5
6 POUR i de 0 à n - 1
7 SI mot[i] <> mot[n - i - 1]
8 RETOURNER FAUX
9 FIN SI
10 FIN POUR
11
12 RETOURNER VRAI
13 FIN FONCTION

est_palindrome_v2() est O(n). Mai elle est Ω(1).

Exercice 3

1 # Approche 1: Vérifier tous les paires sur le tableau

2 FONCTION a_duplication(tableau)
3 n <- taille(tableau)
4
5 POUR i de 0 à n - 2
6 POUR j de i + 1 à n - 1
7 SI tableau[i] = tableau[j]
8 RETOURNER VRAI
9 FIN SI
10 FIN POUR
11 FIN POUR
12
13 RETOURNER FAUX
14 FIN FONCTION

a_duplication() est O(n2 ).

2
 1 # Approche 2: trier la liste est vérifier si il y a un pair à la position i et i + 1 qui contient une
,→ duplication
2
3 FONCTION a_duplication(tableau)
4 n <- taille(tableau)
5 tri_par_fusion(tableau) # O(n*log(n))
6
7 POUR i de 0 à n - 2 # O(n)
8 SI tableau[i] = tableau[i+1]
9 RETOURNER VRAI
10 FIN SI
11 FIN POUR
12
13 RETOURNER FAUX
14 FIN FONCTION

a_duplication_v2() est O(n × log(n)).

Exercice 4

1 # Approche gloutonne
2 FONCTION min_change(somme)
3
4 denom <- [1,2,5,10,20,50,100,200]
5 derniere_denom <- taille(denom) - 1
6 compte <- 0
7
8 TANT QUE somme > 0
9 SI somme > denom[derniere_denom]
10 somme <- somme - denom[derniere_denom]
11 compte <- compte + 1
12 SINON
13 derniere_denom <- derniere_denom - 1
14 FIN SI
15 FIN TANT QUE
16
17 RETOURNER compte
18 FIN FONCTION

min_change() est O(somme). La boucle TANT QUE va faire au plus somme itération.

TD2

3
 Exercice 1

1 FONCTION somme_suite(n)
2 SI n = 1
3 RETOURNER 1
4 SINON
5 RETOURNER 1/n + somme_suite(n - 1)
6 FIN SI
7 FIN FONCTION

somme_suite() est O(n) . On a n appel récursif

Exercice 2

1 FONCTION factorielle(n)
2 SI n = 1
3 RETOURNER 1
4 SINON SI n = 2
5 RETOURNER 2
6 SINON
7 RETOURNER factorielle(n - 1) + factorielle(n - 2)
8 FIN SI
9 FIN FONCTION

factorielle() est O(2n ). Sur chaque étape de récursion, la fonction de la récursion est appelée deux
fois.

Cela veut dire qu’on aura 1 appel après la première étape, 2 = 21 appels après la deuxième étape, 4 = 22
appels après la troisième étape, etc,…

On aura 2n appels dans la dernière étape.

Exercice 3

1 PROCEDURE afficher_tableau(tableau,taille)
2 SI taille > 0
3 afficher_tableau(tableau[taille-1])
4 afficher(tableau[taille-1])
5 FIN SI
6 FIN PROCEDURE

afficher_tableau() est O(n) ou n est la taille du tableau.

4
 Exercice 4

1
2 FONCTION nombre_occurrence(tableau,taille,x)
3 SI taille = 0
4 RETOURNER 0
5 SINON
6 SI tableau[taille] = x
7 RETOURNER 1 + nombre_occurrence(tableau,taille-1,x)
8 SINON
9 RETOURNER nombre_occurrence(tableau,taille-1,x)
10 FIN SI
11 FIN SI
12 FIN FONCTION

nombre_occurrence() est O(n) ou n est la taille du tableau.

Exercice 5

1 FONCTION est_trie(tableau,taille)
2 SI taille =< 1
3 RETOURNER VRAI
4 SINON
5 SI tableau[taille - 1] < tableau[taille - 2]
6 RETOURNER FAUX
7 SINON
8 RETOURNER est_trie(tableau,taille - 1)
9 FIN SI
10 FIN SI
11 FIN FONCTION

est_trie() est O(n).

TD3

Exercice 1

1 # Approche 1: tri par fusion

2
3 FONCTION tri_couleur(tableau)
4 tri_par_fusion(tableau) # O(n log(n))
5 RETOURNER tableau
6 FIN FONCTION

1 FONCTION tri_couleur(tableau)
2 n <- taille(tableau)

5
 3 compteur_zero <- 0
4
5 tableau_trie[n] <- [0,....,0] # de
6
7 # Compter le nombre des zéros
8 POUR i de 0 à n - 1 #O(n)
9 SI tableau[i] = 0
10 compteur_zero <- compteur_zero + 1
11 FIN SI
12 FIN POUR
13
14 # Construction du tableau trié
15 POUR j de 0 à compteur_zero - 1
16 tableau_trie[i] <- 0
17 FIN POUR
18
19 POUR k de compteur_zero à n - 1
20 tableau_trie[i] <- 1
21 FIN POUR
22
23 RETOURNER tableau_trie
24 FIN FONCTION

La deuxième version du tri est O(n). Le tri par compte est efficace sur ce type de problème

Exercice 2

1 # En utilisant l'approche du pivot

2
3 FONCTION k_ieme_petit(tableau,debut,fin,k)
4 SI debut =< fin
5 pivot <- partition(tableau,debut,fin)
6 SI pivot = k - 1
7 RETOURNER tableau[pivot]
8 SINON SI pivot > k - 1
9 RETOURNER k_ieme_petit(tableau , debut , pivot - 1, k)
10 SINON # pivot < k - 1
11 RETOURNER k_ieme_petit(tableau , pivot + 1 , fin , k)
12 FIN SI
13 FIN SI
14 FIN FONCTION
15
16 # Exemple d'appel
17 tab <- [1,2,4,5]
18 k <- 3
19
20 resultat <- k_ieme_petit(tableau, 0, 3, 3)

k_ieme_petit() est O(n2 )

6
 Exercice 3

1 FONCTION intersection(tab_a,tab_b)
2 n <- taille(tab_a)
3 m <- taille(tab_b)
4 resultat <- []
5
6 i <- 0
7 j <- 0
8 k <- 0
9
10 TANT QUE i < n et j < m
11 SI tab_a[i] < tab_b[j]
12 i <- i + 1
13 SINON SI tab_a[i] > tab_b[j]:
14 j <- j + 1
15 SINON # tab_a[i] = tab_b[j]
16 resultat[k] <- tab_a[i]
17 k <- k + 1
18 i <- i + 1
19 j <- j + 1
20 FIN SI
21 FIN TANT QUE
22
23 RETOURNER
24

intersection() est O(n + m).

Exercice 4

1
2 FONCTION somme_deux(tableau,somme)
3
4 debut <- 0
5 fin <- taille(tableau) - 1
6 pair[2] <- [0,0]
7 TANT QUE debut < fin
8 somme_pair = tableau[debut] + tableau[fin]
9
10 SI somme_pair = somme
11 pair[0] <- tableau[debut]
12 pair[1] <- tableau[fin]
13 RETOURNER pair
14 SINON SI somme_pair > somme
15 fin <- fin - 1
16 SINON
17 debut <- debut + 1
18 FIN SI

7
19 FIN TANT QUE
20
21 RETOURNER pair

somme_deux() est O(n) ou n est la taille du tableau.