Scribd
Importer
5 vues3 pages

Exercice

Le document présente une analyse des complexités temporelles des algorithmes itératifs et récursifs, en détaillant les différentes classes de complexité telles que O(n), O(log n), et O(2^n). Il décrit également les types de récursivité, y compris simple, multiple, mutuelle et imbriquée, ainsi que des exemples de procédures récursives avec leurs équations de récurrence. Enfin, il aborde la dérécursivité d'un algorithme.

Transféré par

Mohamed ali Romdhane
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
5 vues3 pages

Exercice

Le document présente une analyse des complexités temporelles des algorithmes itératifs et récursifs, en détaillant les différentes classes de complexité telles que O(n), O(log n), et O(2^n). Il décrit également les types de récursivité, y compris simple, multiple, mutuelle et imbriquée, ainsi que des exemples de procédures récursives avec leurs équations de récurrence. Enfin, il aborde la dérécursivité d'un algorithme.

Transféré par

Mohamed ali Romdhane
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

Partie 1 : itératif

for (int i = 1; i <= n; i++) { while (j <= n) { Si n>0 alors


……………….. j = j * 2; }
for (int j = 1; j <=n ; j++) {
……………….
………
} }
O(log n)
O(n)
Sinon

for (int i = 1; i <= n; i++) {

for (int i = 1; i <= n; i++) {


………………..
……………….
}
}
O(n2)
for (int i = 1; i <= 50; i++) { K=n
……………….. While (k>1){ for (int i = 1; i <= n; i++) {
……………….
} while (j <= n) { Algori( n,m) == n2
j = j * 2; }
O(50)=O(1) K=K/2
}
}
O (Log n * Logn)= O(logn)2
O(n3)

for (int i = 1; i <= n; i++) { While (k<n){

for (int i = 1; i <= n3; i++) { K++


……………….. }
……………….
}
} O(n)

O(n4)

for (int i = 1; i <= 50; i++) { K=n K=n


For (i=1; i<50; i++){ For (i=1; i<m; i++){
for (int i = 1; i <= n; i++) { While (k>1){ While (k>1){
………………..
………………. while (j <= n) { while (j <= n) {
} j = j * 2; } j = j * 2; }
}
50*n = O(n), K=K/2 K=K/2
}} }}

O (50 * Log n * Logn)= O(log n)2 O (m* Log n * Logn)= O(m log2 n)
Partie 2 : Récursif

Type de Récursivité : simple multiple mutuelle imbriqué

Simple ( un seul appel)

Multiple (au moins 2 appels)

Mutuelle (pair impair)

Imbriqué : elle fait appel à elle-même (paramètres)

Terminale : pas de traitement après appel récursif

non terminale il ya un traitement après appel récursif

Type de complexité : (Classe) :

O(n) : linéaire

O(na) : polynomiale

O(logn) logarithmique

O(2N) exponentielle

CAS 1

Procédure DoubleRecursion(n)
Si n <= 0 alors
Retourner ………..
Sinon
DoubleRecursion(n - 1)
DoubleRecursion(n - 1)
FinSi
FinProcédure

Type Multiple , Terminale


2 appels
Equation de récurrence C(n) = 2 C(n-1) + O(1)

Résoudre l’equation :

C(n) = 2 C(n-1) = 2*2 C(n-2) =2* 2*2*….. C(n-3) ===== 2N C(0) = O(2N)

Exponentiel

CAS 2
Procédure DoubleRecursion(n)
Si n <= 1 alors
retourner
Sinon
DoubleRecursion(n / 2)
DoubleRecursion(n / 2)
FinSi
FinProcédure

T(n)= 2 T(n/2) + O(1)

La complexité : O (n)

T(n) = a T(n/b) + O(nk)

CAS 3

Procédure DoubleRecursion(n)
Si n <= 0 alors
Retourner ………..
Sinon
DoubleRecursion(n - 1)
DoubleRecursion(n - 1)
FinSi
for (int i = 1; i <= n; i++) {
………………..
……………….
}

FinProcédure

Equation de récurrence C(n) = 2 C(n-1) + O(n)

C(n-1) = 2 C(n-2) + O(n)

Résoudre l’equation :

C(n) = 2 C(n-1) +O(n) = O(N2N+2N )

Exponentiel

Dérécursiver un algorithme : Voir la feuille distribuée en cours

Vous aimerez peut-être aussi