Bonjour à tous, je passe devant le grand jury dans 2h et j'ai un petit problème, je ne comprend pas exactement ce qu'est la complexité. Pourriez-vous me l'expliquer ???
Posted by: Rain'
En gros si tu pars d'un tableau de taille n, la complexité c'est le nombre d'opérations élémentaires qu'il te faudra faire pour trier ton tableau en fonction de n.
Elle s'exprime généralement en grand O, O(n), O(n log n), O(n²) ....
O(n) ça veut dire qu'il existe K tel que pour tout n, tu feras moins de K*n opérations. Concrètement ça veut dire que tu parcoures une unique fois les valeurs de ton tableau.
Posted by: SimonB
Ajoutons que le "mieux", c'est une complexité logarithmique (O(log n)), parce que le logarithme, ça croît relativement lentement, ce qui est assez sympathique pour traiter des données :)
Posted by: Fanfan
merci pour vos réponses ! Ils existent les tris naïfs et complexes. Notre étude montre les tris naïfs sont en gros O(n²) et les tris complexes O(n(ln n)). Quelle est le lien entre la complexité et "dans le meilleur des cas", "le pire", "cout moyen" et " cout exact" ???
Posted by: Rain'
Citation:
Posté par SimonB
une complexité logarithmique (O(log n))
Avec un petit n en plus, sinon c'est un peu juste non ?
Posted by: Fanfan
oui merci c'est exact
Posted by: Fanfan
s'il vous plait !! :)
Posted by: Rain'
Le lien, euh, tu te rapproches du meilleur des cas quand la complexité diminue et c'est de pire en pire quand elle augmente. Typiquement vaut mieux du O(n ln n ) que du O(n²) car n ln n = o(n²) quand n->+inf.
En français ça veut dire que tu as besoin de beaucoup moins de calculs et donc de temps et de mémoire pour accomplir ton algorithme.