OK. visiblement il y a des problemes de comprehension des notations de complexites. Les notations Big-Oh, Big-Theta, et Big-Omega sont des notations ensemblistes qui representent toutes les fonctions qui sont dans l'ensemble. Elles n'ont rien a voir avec le pire cas ou le meilleur cas, ou le cas moyen.
La notation Big-Oh veut basiquement dire que si f est dans O(g) alors f(n) <= g(n) [de facon asymptotique, voir ton cours pour la definition exacte]. O(g) est l'ensemble de toute les fonctions f tel que f(n) <= g(n). Du fait tu as n^3 dans O(n^3), mais aussi n+5 est dans O(n^3), et n^2 log (n) est aussi dans O(n^3)..
De la meme facon Omega(g) est l'ensemble des fonctions f tel que f(n) >= g(n). Du fait n^3 est dans Omega(n^3), mais n^12 est aussi dans Omega(n^3) et 2^(n!) est aussi dans Omega(n^3).
Si f est dans Theta(g) alors f est dans Omega(g) et dans O(g).
Dans tous les cas, tu prefererais pouvoir exprime tout avec une notation Big-Theta parceque c'est la notation la plus precise. Mais des fois on ne sait pas faire alors on se contente des notations Big-Oh et Big-Omega.
Quel rapport avec les complexite au pire cas et au meilleur cas, et en moyenne? En general on exprime ces complexites dans ces notations ensemblistes parceqeu c'est plus simple.
Prenons un exemple concret:
bubblesort(A, n) {
bool cont = true;
while (cont) {
cont = false;
for (int i=1;i<n; ++i)
if (A[i] > A[i-1]) {
swap(A[i], A[i-1]);
cont = true;
}
}
}
C'est un algo de tri. On peut prouver que dans le pire cas, il y a n-1 iterations de la boucle while.
Et donc il y a danss le pire cas en gros n^2 execution du if, et le contenu du if est constant. Donc la complexite au pire cas est dans Theta(n^2). Elle est aussi dans O(n^2), et dans Omega(n^2). Et note qu'elle est aussi dans Omega(1) et dans O(n^42).
Dans le meilleur cas, il n'y qu'une seule execution de la boucle while. Et donc la complexite au meilleur cas est de Theta(n). Note que la complexite au meilleur cas est aussi dans O(n^2) ou dans O(2^n).
La notation Big-Oh et Big-Omega est decorelle de si tu fais une analyse au pire cas ou au meilleur cas.
Pourquoi est ce qu'on n'utiliserait pas toujours Big-Theta? On utilise pass toujours Big-Theta parceque des fois, c'est difficile de prouver qu'on est vraiment en Big-Theta. Consider le code suivant:
strange(A, n) {
if (A[0] == 0) return;
bool cont = true;
for (int j=0; j<n; ++j) {
if (strangeconditionIcannotanalysebutinO1(j)) {
for (int i=1;i<n; ++i) {
if (A[i] > A[i-1]) {
swap(A[i], A[i-1]);
}
}
}
}
}
Maintenant c'est beaucoup plus difficile d'analyser cet algorithme. parceque je ne sais pas combien de fois la boucle i va etre executer. Si je ne sais pas analyse la condition qui est au milieu, alors la seule chose que je puisse dire est que la boucle i va s'executer entre 0 fois et n fois. Donc je suis sur que la complexite au pire cas est en O(n^2) parceque clairement la condition ne peut etrer vrai que n fois au plus. Mais je ne sais pas dire si au pire cas c'est possible la condition soit vrai n fois. Donc je ne sais pas si la complexite au pire cas est dans Omega(n^2).
Note que meme si la condition est toujours fausse alors, il faudra quand meme faire la condition bizarre n fois. Du fait la complexite au pire cass est aussi en Omega(n).
Donc je me resoud a dire que l'algo est en O(n^2) et dans Omega(n) parceque je ne sais pas faire l'analyse de facon plus precise que ca.
Et note que la complexite au meilleur cas est dans Theta(1)
