Discussion :

[nehm33]

Bonjour j'ai quelques difficultés en complexité. je voudrais savoir comment calculer la complexité de la fonction suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
fonction devine1(ch,chaine) :
       si longueur(ch) > longueur(chaine) :
             retourner Faux
       pour i allant de 0 à longueur(chaine) – longueur(ch) :
             j <- 0
             tant que j < longueur(ch) et ch[j] = chaine[i+j] :
                        j <- j+1
                        si j = longueur(ch) :
                                retourner i
        retourner rien

[BufferBob]

salut,

de ce que j'ai pu comprendre de la notion de complexité, les traitements uniques ne sont pas pris en compte, le if ici ne change pas radicalement le déroulé de la fonction, et finalement ce qui est vraiment gourmand en temps c'est la boucle for, laquelle dépend des paramètres passés à la fonction, donc sauf erreur je dirais qu'on est face à une complexité en O(n)

[nehm33]

c'est quoi le n

Je tiens à rappeler la boucle tant que est imbriquée dans la boucle for

[tbc92]

Le n, c'est a priori la longueur de la 2ème chaine (celle qui s'appelle chaine dans le code, et qui est a priori la plus longue)

Et quand Bufferbob dit que la complexité est en O(n), ça veut dire que si on lance plein de fois cette procédure avec des chaines de 10000 caractères, on va avoir un certain temps de traitement, Si on relance la même procédure plein de fois, avec des chaines de 20000 caractères, on aura un nouveau temps de traitement, et O(n), ça veut dire : quand je multiplie la longueur des chaines par 2, le temps de traitement se multiplie aussi par 2.

[nehm33]

Moi je pensais plutôt que sa complexité était O(nN) où n et N sont les longueurs des deux chaines

[pseudocode]

Moi je pensais plutôt que sa complexité était O(nN) où n et N sont les longueurs des deux chaines

Oui, c'est cela.

L'algo fera au maximum (N-n)*n comparaisons de caractères.
C'est l'implémentation naïve de l'algo pour la fonction strstr().

[BufferBob]

Je tiens à rappeler la boucle tant que est imbriquée dans la boucle for

oui, bizarrement je l'ai complètement loupée cette boucle imbriquée ce matin, les yeux qui fatiguent peut-être..

par ailleurs on me dit "normalement on dirait O(n m), mais comme m est borné par n, O(n²) c'est correct", mais je ne suis pas à même de déterminer si c'est valide ou non par rapport à la réponse de pseudocode

[pseudocode]

par ailleurs on me dit "normalement on dirait O(n m), mais comme m est borné par n, O(n²) c'est correct", mais je ne suis pas à même de déterminer si c'est valide ou non par rapport à la réponse de pseudocode

m n'est pas "borné" par n, puisque ce sont deux variables libres. On peut y mettre ce qu'on veut.

C'est vrai que si m>n alors l'algo retourne FAUX directement et donc est O(1).
Dans les autres cas, il est O(nm) avec m<=n, et donc O(n²)

Mathématiquement, O() désigne une domination asymptotique.
Donc si un algo est O(n), il est aussi O(n²), O(n^3), O(n.log(n)), ... et n'importe quoi plus grand que "n".

Généralement, on cherche plutot à fournir Theta() qui désigne un équivalence asymptotique.
Mais comme c'est mathématiquement compliqué, on se limite a fournir le plus "petit" O() parmi les complexités usuelles

[BufferBob]

merci de cette précision

[tbc92]

oui, bizarrement je l'ai complètement loupée cette boucle imbriquée ce matin, les yeux qui fatiguent peut-être..

Ce matin, le code était très difficile à lire, parce qu'il n'y avait pas la balise code. Et donc pas d'indentation en particulier.