Faudrait p'tet développer un peu là. Le monsieur te dit qu'il n'est pas informaticien, alors parler d' « algo en n*log(n) » hein... En plus là tu fais implicitement référence à une complexité de l'algorithme en temps, mais la complexité en espace compte parfois tout autant, voire plus.
Donc, pour clarifier : un algorithme s'exécute en un temps donné (d'après le nombre des entrées qu'on lui fournit), et prend une certaine place en mémoire (donc de l'espace mémoire). Lorsqu'on dit qu'un algo se déroule en n.log(n), on veut dire que si on a n entrées, on mettra un temps de n.log(n) [1] à exécuter l'algorithme (dans ce cas, on a implicitement pensé au pire des cas - dans le meilleur des cas, l'algorithme se débrouille peut-être mieux).
Donc pour résumer : si j'ai deux algorithmes qui résolvent le même problème, et que le premier possède une complexité en temps de n.log(n), alors que l'autre fait du n^3 (n cube), on se retrouve très vite avec une différence de temps d'exécution énorme.
Pour ce qui est de la théorie des graphes, c'est effectivement des maths, mais ce sont quand même des maths « faciles » (bon ok, moi, je suis nul, mais les vrais matheux n'ont pas trop de mal autour de moi). Par contre, il suffit de pousser un chouilla plus loin, et l'informaticien (même ingénieur) risque de se retrouver un peu perdu.
Une dernière chose : même si je suis globalement d'accord avec toi, la plupart des matheux que je connais (càd qui ont un deug MIAS ou une prépa MP derrière eux) ne considèrent pas l'analyse numérique comme des maths.
[1] J'ai volontairement mis de côté l'unité de temps, puisque tout dépend des types de données manipulées.
[^] # Re: En vrac
Posté par lasher . En réponse au journal Écoles, classes prépas etc etc.... Évalué à 3.
Donc, pour clarifier : un algorithme s'exécute en un temps donné (d'après le nombre des entrées qu'on lui fournit), et prend une certaine place en mémoire (donc de l'espace mémoire). Lorsqu'on dit qu'un algo se déroule en n.log(n), on veut dire que si on a n entrées, on mettra un temps de n.log(n) [1] à exécuter l'algorithme (dans ce cas, on a implicitement pensé au pire des cas - dans le meilleur des cas, l'algorithme se débrouille peut-être mieux).
Donc pour résumer : si j'ai deux algorithmes qui résolvent le même problème, et que le premier possède une complexité en temps de n.log(n), alors que l'autre fait du n^3 (n cube), on se retrouve très vite avec une différence de temps d'exécution énorme.
Pour ce qui est de la théorie des graphes, c'est effectivement des maths, mais ce sont quand même des maths « faciles » (bon ok, moi, je suis nul, mais les vrais matheux n'ont pas trop de mal autour de moi). Par contre, il suffit de pousser un chouilla plus loin, et l'informaticien (même ingénieur) risque de se retrouver un peu perdu.
Une dernière chose : même si je suis globalement d'accord avec toi, la plupart des matheux que je connais (càd qui ont un deug MIAS ou une prépa MP derrière eux) ne considèrent pas l'analyse numérique comme des maths.
[1] J'ai volontairement mis de côté l'unité de temps, puisque tout dépend des types de données manipulées.