Version imprimable
Salut les devlopeurs ,
j'ai des question :
1/ C'est quoi la déffirence entre la compléxité asymptotiqe et la compléxité uniforme .
2/ Pour quoi nous calculons pas la complexité au mieux ? pour quoi toujours on calcule la compléxité au pire de cas ?
3/ la définition du notion Laundu c'est : F(x) = 0(g(x)) , c'est à dire f(x) < g(x) . c , tell que c>n0 .
ma question , c'est quoi le n0 ???
et merci
:salut:
Dans quel contexte as-tu vu cette notion de "complexité uniforme" ? Je n'en trouve pas de trace sur Internet, en tout cas…Citation:
Envoyé par Karimce
Quelle information t'apporterait cette complexité dans le meilleur cas ? Le temps minimum d'exécution de l'algorithme (en supposant une complexité temporelle). En fait, deux autres complexités sont plus intéressantes : celle dans le pire cas (le nombre d'opérations maximal que prendra l'algorithme) et celle dans le cas moyen (en moyenne, peu importe l'entrée, ce que fera l'algorithme). À l'exécution, tu auras une très bonne idée du temps que prendra ton algorithme, avec des variations : si c'est plus rapide, tant mieux ; si c'est plus lent, il est intéressant de savoir à quel point.Citation:
Envoyé par Karimce
C'est lié à la notion de complexité asymptotique : tu étudies un algorithme quand les entrées deviennent très grandes.
Non, la relation avec n0 est x > n0 (c est simplement positif et non nul). Tu imposes que l'inégalité soit valide pour des x "suffisamment grands", des entrées suffisamment grandes à ton algorithme (sous-entendu : pour des instances trop petites, le temps pris est négligeable).Citation:
Envoyé par Karimce
Bonjour,Citation:
Envoyé par Karimce
On ne calcule pas toujours la complexité «au pire des cas». Par exemple, dans le cas classique des tris et de leur complexité en temps on peut remarquer qu'on arrive à déterminer que dans le cas du tri par insertions on a une complexité dans le pire des cas en O(n²) comparaisons, O(n) comparaisons dans le meilleur des cas, et O(n²) comparaisons en moyenne. Mais aussi O(n²) dans le pire des cas en échanges, O(1) dans le meilleur des cas, et O(n²) en moyenne. On pourra aussi s'intéresser à la complexité spatiale.
On s'intéresse souvent à la complexité en moyenne, ou en temps amorti, pour avoir une idée globale de la réaction de l'algorithme lorsqu'il y a de plus en plus de données à traiter. La complexité au pire nous permet d'estimer ce à quoi on peut s'attendre au pire.
Toujours dans le cas des tris, quicksort a une complexité en temps au pire de O(n²) en comparaisons, pourtant en moyenne on a une complexité en moyenne de O(n.log n). Si la complexité en temps au pire était le seul critère on n'utiliserait pas souvent quicksort ^^.
Maintenant je pourrais aussi interpréter ta question comme : «pourquoi n'utilise-t-on que le O et pas 𝛺 ou 𝛷 ?
Souvent parce qu'on ne peut pas faire mieux :)
Toujours pour en revenir au tri, on peut prouver relativement simplement qu'un algorithme de tri par comparaisons ne pourra jamais faire mieux en temps O(n log n) comparaisons dans le pire des cas.