Discussion :

[sympho]

Bonjour à tous,

Si dans un programme je fais appel successivement à 2 algos de complexité respective X et Y, quelle est la complexité résultante ?

A chaque fois l'appel est effectué sur la même structure de taille N.

Je songe à Z = max(X, Y), mais pas sûr.

algoComplexitéX() {}

algoComplexitéY() {}

algoComplexitéZ() {
algoComplexitéX()
algoComplexitéY()
}

Merci.

PS : Un exemple peut-être deux boucles for successsives sur un même tableau.

[kwariz]

Bonsoir,

Dans toute la suite je vais utiliser une notation ensembliste pour décrire une complexité et je vais juste prendre d'autres noms pour les algos :
Nous avons donc un algorithme A de complexité CA(n)∈O(f(n)) et un algorithme B de complexité CB(n)∈O(g(n)). Si tu construis l'algorithme AB qui est simplement l'exécution de A suivie de l'exécution de B chacun avec des données de taille n, alors la complexité cumulée CAB(n) est bien CAB(n)∈O(max(f,g)(n)), avec la définition usuelle de max pour des fonctions comparables etc ... :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
max(f,g) = | f, si ∃ N∈ℕ tq ∀ n>N on a f(n)≥g(n)
           | g, si ∃ N∈ℕ tq ∀ n>N on a g(n)≥f(n)

Maintenant il peut arriver que tu n'obtiennes pas la meilleure borne dans le cas où tu donnes la sortie de A comme entrée de B.
Prenons pour algorithme A le tri par tas HEAPSORT et pour algorithme B le tri par insertion INSERTIONSORT en mesurant la complexité usuelle mesurant le nombre de comparaisons d'élements, la taille de l'entrée est donnée par le nombre d'éléments du tableau.
Nous avons donc CA(n)∈O(n log n) et CB(n)∈O(n²), ici nous avons dans le cas général CAB(n)∈O(n²) par application de la formule du max.
Néanmoins si l'entrée de B est la sortie de A nous avons le cas particulier du tri d'un tableau déjà trié qui est en O(n) pour INSERTIONSORT, et toujours dans ce cas particulier nous aurons donc CAB(n)∈O(n log n)⊂O(n²)

[sympho]

Merci kwariz