J'ai un petit souci avec cette notion en programmation.
Est-ce qu'elle doit obligatoirement être accompagnée d'une solide base
mathématique? Parceque daprès ce que j'ai pu en lire, ça ressemble à des
maths, mais un peu au dessus de ce qu'on fait en deuxième année de Fac.
quand j'ai tenté d'en parlé à mon prof, il m'a gentiment suggéré de finir
la feuille de TD qu'il nous a soumi d'abord. Il a raison, mais moi j'ai un
truc qui me trote dans la tête....
Donc ce que j'ai pu conclure déjà c'est qu'on ne pas parler de complexité
dans tous les langages. Par exemple parler de complexité en assembleur
n'est pas possible. N'est-ce pas?
Ensuite, la compléxité permet de mesurer/déduire "à quelle vitesse" le
bloc d'instructions va être executé. C'est ça? donc en fait, tous les
langages sont équivalents. Ce qui me semble improbable, donc il est
évident que je n'ai pas compris un truc.
En pensant encore plus profondément à la chose, je me suis dit que la
compléxité est plus palpable quand on programme avec un langage
fonctionnel. D'ailleurs, j'ai remarqué que la notion de compléxité est
plus souvent évoquée dans les groupes dédiés que dans ceux pour les
langages proceduraux.
Et enfin, il y a un dernier truc: dans certains langages, la vitesse
parcours d'une séquence immuable est différente de celle de parcours d'une
séquence modifiable. Ca veut dire que pour optimiser, il n'y a pas que la
compléxité à prendre en compte, il y a aussi le "très bas niveau" du
langage dans lequel on développe.
Au final, je ne suis convaincu par aucune des explications que j'essaie de
me faire. Les documents sur la compléxité que j'ai lu abordent des notions
mathématiques que je n'arrive pas encore à suivre.
Si vous avez un moyen de m'aider à comprendre, je vous serait
reconnaissant.
Pour entrer plus dans les détails, je souhaite m'interesser aux langages
C, Python et Ocaml dans mon avenir.
Attention, le suivi est positionné sur un groupe généraliste. Mais je suis
abonné à tous les groupes du crosspost, donc un refus de suivi ne me
gènerait pas plus que ça, si vous le souhaitez.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Pierre Maurette
Bonjour, [...]
Attention, le suivi est positionné sur un groupe généraliste. Mais je suis abonné à tous les groupes du crosspost, donc un refus de suivi ne me gènerait pas plus que ça, si vous le souhaitez. Ne vous vexez pas, je ne botte pas en touche. Je n'ai pas lu
*attentivement* votre message, ça fera peut-être un joli fil sur fclc. Mais dans le suivi ne figure pas le groupe qui me semble le plus adapté à votre question: fr.comp.algorithmes
-- Pierre Maurette
Bonjour,
[...]
Attention, le suivi est positionné sur un groupe généraliste. Mais je suis
abonné à tous les groupes du crosspost, donc un refus de suivi ne me
gènerait pas plus que ça, si vous le souhaitez.
Ne vous vexez pas, je ne botte pas en touche. Je n'ai pas lu
*attentivement* votre message, ça fera peut-être un joli fil sur fclc.
Mais dans le suivi ne figure pas le groupe qui me semble le plus adapté
à votre question:
fr.comp.algorithmes
Attention, le suivi est positionné sur un groupe généraliste. Mais je suis abonné à tous les groupes du crosspost, donc un refus de suivi ne me gènerait pas plus que ça, si vous le souhaitez. Ne vous vexez pas, je ne botte pas en touche. Je n'ai pas lu
*attentivement* votre message, ça fera peut-être un joli fil sur fclc. Mais dans le suivi ne figure pas le groupe qui me semble le plus adapté à votre question: fr.comp.algorithmes
-- Pierre Maurette
Laurent Deniau
Pierre Maurette wrote:
Bonjour,
[...]
Attention, le suivi est positionné sur un groupe généraliste. Mais je suis abonné à tous les groupes du crosspost, donc un refus de suivi ne me gènerait pas plus que ça, si vous le souhaitez.
Ne vous vexez pas, je ne botte pas en touche. Je n'ai pas lu *attentivement* votre message, ça fera peut-être un joli fil sur fclc. Mais dans le suivi ne figure pas le groupe qui me semble le plus adapté à votre question: fr.comp.algorithmes
Parce qu'il ne sait pas que la complexite releve de l'algorithmique et non d'un langage...
a+, ld.
Pierre Maurette wrote:
Bonjour,
[...]
Attention, le suivi est positionné sur un groupe généraliste. Mais je
suis
abonné à tous les groupes du crosspost, donc un refus de suivi ne me
gènerait pas plus que ça, si vous le souhaitez.
Ne vous vexez pas, je ne botte pas en touche. Je n'ai pas lu
*attentivement* votre message, ça fera peut-être un joli fil sur fclc.
Mais dans le suivi ne figure pas le groupe qui me semble le plus adapté
à votre question:
fr.comp.algorithmes
Parce qu'il ne sait pas que la complexite releve de l'algorithmique et
non d'un langage...
Attention, le suivi est positionné sur un groupe généraliste. Mais je suis abonné à tous les groupes du crosspost, donc un refus de suivi ne me gènerait pas plus que ça, si vous le souhaitez.
Ne vous vexez pas, je ne botte pas en touche. Je n'ai pas lu *attentivement* votre message, ça fera peut-être un joli fil sur fclc. Mais dans le suivi ne figure pas le groupe qui me semble le plus adapté à votre question: fr.comp.algorithmes
Parce qu'il ne sait pas que la complexite releve de l'algorithmique et non d'un langage...
a+, ld.
Jean-Marc Bourguet
Copie en plus sur fr.comp.algorithmes, suivi uniquement sur fr.comp.lang.general, fr.comp.algorithmes.
R12y writes:
Donc ce que j'ai pu conclure déjà c'est qu'on ne pas parler de complexité dans tous les langages. Par exemple parler de complexité en assembleur n'est pas possible. N'est-ce pas?
Et voila Knuth qui se retournerait dans sa tombe, s'il y etait deja. (Voir dans _The Art Of Computer Programming_ pourquoi il utilise un assembleur et non un autre langage). Non, la complexite est une caracteristique de l'algorithme et on peut la calculer en n'importe quel langage. La calculer en assembleur a meme quelques avantages en ce sens que le cout d'une instruction y est un peu plus facile a determiner qu'avec un langage de haut niveau (surtout a l'epoque ou Knuth a ecrit son livre, depuis les choses se sont compliquees pour l'assembleur egalement).
Le calcul de complexite c'est determiner a quelle vitesse grandi le nombre d'instructions a executer quand un parametre (generalement la taille des donnees, mais ce peut etre la taille du resultat quand on fait par exemple un calcul des decimales de pi) augmente. On peut faire aussi un calcul de complexite pour la quantite de memoire necessaire.
Si on dit qu'un algorithme de tri a une complexite de O(n) ca veut dire (en gros) que si on double la taille des donnees, on double le temps necessaire pour executer l'algorithme. Si on a un algorithem en O(n log n), doubler la taille des donnees va faire un peu plus que doubler le temps necessaire. Avec algorithme en O(n^2), doubler la taille des donnees va quadrupler le temps necessaire...
Ce n'est pas parce qu'un algorithme a une meilleure complexite qu'il sera plus rapide pour un cas donne parce qu'on ne tient pas compte des termes qui sont negligeables pour une grande valeur du parametre. Si la valeur du parametre est suffisemment petite (ce qui est parfois le cas de toute valeur pratique), il se peut que l'algorithme avec la mauvaise complexite soit plus efficace.
D'autre part, on ne tient pas compte des constantes multiplicatives, s'il faut 10000 n operations ou seulement 2 n operations, la complexite est la meme. Mais je sais quel algorithme je prefererais utiliser.
Le fait qu'on neglige les constantes multiplicatives montre que le choix du langage est independant de la complexite.
Je crois que ceci reponds en gros a tes questions.
En pensant encore plus profondément à la chose, je me suis dit que la compléxité est plus palpable quand on programme avec un langage fonctionnel. D'ailleurs, j'ai remarqué que la notion de compléxité est plus souvent évoquée dans les groupes dédiés que dans ceux pour les langages proceduraux.
Le groupe le plus adapte pour parler de complexite est fr.comp.algorithmes. Dans les autres, ca devrait generalement venir plutot d'une derivee de la conversion ou pour un point accessoire.
A+
-- Jean-Marc Site de usenet-fr: http://www.usenet-fr.news.eu.org
Copie en plus sur fr.comp.algorithmes, suivi uniquement sur
fr.comp.lang.general, fr.comp.algorithmes.
Donc ce que j'ai pu conclure déjà c'est qu'on ne pas parler de
complexité dans tous les langages. Par exemple parler de complexité
en assembleur n'est pas possible. N'est-ce pas?
Et voila Knuth qui se retournerait dans sa tombe, s'il y etait deja.
(Voir dans _The Art Of Computer Programming_ pourquoi il utilise un
assembleur et non un autre langage). Non, la complexite est une
caracteristique de l'algorithme et on peut la calculer en n'importe
quel langage. La calculer en assembleur a meme quelques avantages en
ce sens que le cout d'une instruction y est un peu plus facile a
determiner qu'avec un langage de haut niveau (surtout a l'epoque ou
Knuth a ecrit son livre, depuis les choses se sont compliquees pour
l'assembleur egalement).
Le calcul de complexite c'est determiner a quelle vitesse grandi le
nombre d'instructions a executer quand un parametre (generalement la
taille des donnees, mais ce peut etre la taille du resultat quand on
fait par exemple un calcul des decimales de pi) augmente. On peut
faire aussi un calcul de complexite pour la quantite de memoire
necessaire.
Si on dit qu'un algorithme de tri a une complexite de O(n) ca veut
dire (en gros) que si on double la taille des donnees, on double le
temps necessaire pour executer l'algorithme. Si on a un algorithem en
O(n log n), doubler la taille des donnees va faire un peu plus que
doubler le temps necessaire. Avec algorithme en O(n^2), doubler la
taille des donnees va quadrupler le temps necessaire...
Ce n'est pas parce qu'un algorithme a une meilleure complexite qu'il
sera plus rapide pour un cas donne parce qu'on ne tient pas compte des
termes qui sont negligeables pour une grande valeur du parametre. Si
la valeur du parametre est suffisemment petite (ce qui est parfois le
cas de toute valeur pratique), il se peut que l'algorithme avec la
mauvaise complexite soit plus efficace.
D'autre part, on ne tient pas compte des constantes multiplicatives,
s'il faut 10000 n operations ou seulement 2 n operations, la
complexite est la meme. Mais je sais quel algorithme je prefererais
utiliser.
Le fait qu'on neglige les constantes multiplicatives montre que le
choix du langage est independant de la complexite.
Je crois que ceci reponds en gros a tes questions.
En pensant encore plus profondément à la chose, je me suis dit que
la compléxité est plus palpable quand on programme avec un langage
fonctionnel. D'ailleurs, j'ai remarqué que la notion de compléxité
est plus souvent évoquée dans les groupes dédiés que dans ceux pour
les langages proceduraux.
Le groupe le plus adapte pour parler de complexite est
fr.comp.algorithmes. Dans les autres, ca devrait generalement venir
plutot d'une derivee de la conversion ou pour un point accessoire.
A+
--
Jean-Marc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Copie en plus sur fr.comp.algorithmes, suivi uniquement sur fr.comp.lang.general, fr.comp.algorithmes.
R12y writes:
Donc ce que j'ai pu conclure déjà c'est qu'on ne pas parler de complexité dans tous les langages. Par exemple parler de complexité en assembleur n'est pas possible. N'est-ce pas?
Et voila Knuth qui se retournerait dans sa tombe, s'il y etait deja. (Voir dans _The Art Of Computer Programming_ pourquoi il utilise un assembleur et non un autre langage). Non, la complexite est une caracteristique de l'algorithme et on peut la calculer en n'importe quel langage. La calculer en assembleur a meme quelques avantages en ce sens que le cout d'une instruction y est un peu plus facile a determiner qu'avec un langage de haut niveau (surtout a l'epoque ou Knuth a ecrit son livre, depuis les choses se sont compliquees pour l'assembleur egalement).
Le calcul de complexite c'est determiner a quelle vitesse grandi le nombre d'instructions a executer quand un parametre (generalement la taille des donnees, mais ce peut etre la taille du resultat quand on fait par exemple un calcul des decimales de pi) augmente. On peut faire aussi un calcul de complexite pour la quantite de memoire necessaire.
Si on dit qu'un algorithme de tri a une complexite de O(n) ca veut dire (en gros) que si on double la taille des donnees, on double le temps necessaire pour executer l'algorithme. Si on a un algorithem en O(n log n), doubler la taille des donnees va faire un peu plus que doubler le temps necessaire. Avec algorithme en O(n^2), doubler la taille des donnees va quadrupler le temps necessaire...
Ce n'est pas parce qu'un algorithme a une meilleure complexite qu'il sera plus rapide pour un cas donne parce qu'on ne tient pas compte des termes qui sont negligeables pour une grande valeur du parametre. Si la valeur du parametre est suffisemment petite (ce qui est parfois le cas de toute valeur pratique), il se peut que l'algorithme avec la mauvaise complexite soit plus efficace.
D'autre part, on ne tient pas compte des constantes multiplicatives, s'il faut 10000 n operations ou seulement 2 n operations, la complexite est la meme. Mais je sais quel algorithme je prefererais utiliser.
Le fait qu'on neglige les constantes multiplicatives montre que le choix du langage est independant de la complexite.
Je crois que ceci reponds en gros a tes questions.
En pensant encore plus profondément à la chose, je me suis dit que la compléxité est plus palpable quand on programme avec un langage fonctionnel. D'ailleurs, j'ai remarqué que la notion de compléxité est plus souvent évoquée dans les groupes dédiés que dans ceux pour les langages proceduraux.
Le groupe le plus adapte pour parler de complexite est fr.comp.algorithmes. Dans les autres, ca devrait generalement venir plutot d'une derivee de la conversion ou pour un point accessoire.
A+
-- Jean-Marc Site de usenet-fr: http://www.usenet-fr.news.eu.org
