Bonjour, ce serait pour savoir si vous auriez des astuces ou des liens (cours, tutoriel) pour comprendre comment évaluer la complexité moyenne, ainsi que la complexité au pire d'un algorithme.

Par exemple si on a 2 algorithmes qui font la même tâche (ex : trier une liste ou autre chose), comment je peux savoir, en regardant l'algorithme, si ce dernier à une complexité logarithmique, linéaire, quadratique...
contexte : SpoilAfficherMasquer(On a un cours d'algorithmique à la fac, et il y a pas mal de chance qu'il y ait des questions de ce type (quel est la complexité au pire de cet algorithme ?) au partiel, mais je ne suis vraiment pas sûr de la méthode à utiliser)

Merci en tous cas !

Malheureusement si on avait une façon de calculer la complexité d'un algorithme sans réfléchir (via un algorithme donc) le problème de l'arrêt serait résolu

Corollaire immédiat : il faut réfléchir

Le 06 novembre 2021 à 17:03:46 :
Malheureusement si on avait une façon de calculer la complexité d'un algorithme sans réfléchir (via un algorithme donc) le problème de l'arrêt serait résolu

Corollaire immédiat : il faut réfléchir

Je vois, il n'y a pas de méthode à appliquer du coup, je me souviens qu'il y avait un truc avec le nombre d'opérations, où un truc sur les variables, mais je ne suis plus sûr du coup.

Le 06 novembre 2021 à 15:31:27 :
Bonjour, ce serait pour savoir si vous auriez des astuces ou des liens (cours, tutoriel) pour comprendre comment évaluer la complexité moyenne, ainsi que la complexité au pire d'un algorithme.

Par exemple si on a 2 algorithmes qui font la même tâche (ex : trier une liste ou autre chose), comment je peux savoir, en regardant l'algorithme, si ce dernier à une complexité logarithmique, linéaire, quadratique...
contexte : SpoilAfficherMasquer(On a un cours d'algorithmique à la fac, et il y a pas mal de chance qu'il y ait des questions de ce type (quel est la complexité au pire de cet algorithme ?) au partiel, mais je ne suis vraiment pas sûr de la méthode à utiliser)

Merci en tous cas !

Il n'y a qu'une seule facon de faire ca. Il faut analyser le code et compter les operations. Apres il y a des techniques d'analyse plus ou moins rafiner. Mais toutes les techniques reviennent a "il faut compter". Et il y a des techniques simple qui s'apprennent en une heure et des techniques complique qui peuvent mettre des semaines a etre compris. En principe un des but principaux d'un cours d'algo est d'apprendre comment faire cette analyse.

La technique la plus simple pour les codes base de boucles est d'estimer le pire cas du nombre d'iteration d'une execution de la boucle et tu multiplie le nombre d'iteration de la boucle par le cout au pire de ce qu'il y a dans la boucle. Et si tu as deux instructions l'une apres l'autre tu ajoute leurr cout.
Ex:

for (i=0;i<n:++i)
  sum +=i

tu fait un pire n tour de boucle. chauqe tour de boucle coute au pire 1. Ca te donne O(n)*O(1) = O(1)

for (i=0;i<n:++i)
  for (j=0; j<n; ++j)
    sum += i

Ca premiere boucle fait un pire n iteration, la deuxieme qui est imbrique fait aussi au pire n iteration, ce qu'il a dedans, coute 1. Ca donne O(n)*O(n)*O(1) = O(n^2)

for (i=0;i<n:++i)
  for (j=0; j<i; ++j)
    sum += i

Ca premiere boucle fait un pire n iteration, la deuxieme qui est imbrique fait aussi au pire i iterations, mais comme ca a l'air complique et qu'on a i<n on va compte n operations, ce qu'il a dedans, coute 1. Ca donne O(n)*O(n)*O(1) = O(n^2)

for (i=0;i<n:++i)
  if (i is prime)
    for (j=0; j<i; ++j)
      sum += i

Ca premiere boucle fait un pire n iteration, la deuxieme qui est imbrique n'est execute que si i est premier, mais comme ca a l'air complique et qu'on a i<n on va compte n operations, ce qu'il a dedans, coute 1. Ca donne O(n)*O(n)*O(1) = O(n^2)

Probablement on peut analyser ce code mieux si on sait les proprietes des nombres premiers. Mais en premiere approx c'est ca qu'on va faire. Si on sait compter le nombre de nombre premier on peut faire une analyse plus intelligente. Mais comme on utilise la notation O, l'analyse est correcte meme si il y a une analyse meilleur.

Pour faire de l'analyse en moyenne on fait pareil mais a partir d'une description probabiliste des parametres de l'algorithme et tu appliques la formule de moyenne que tu as appris en 2nde E[x]=somme pour tout x' possible P(x')*x'

Pour les algo recursif, en general tu exprimes la complexite recursivement et tu resouds la recurence. Souvent le master s'applique.

Apres ca je ne sais pas quoi te dire de plus que regardes les differente technique dans ton cours d'algo. Ou si tu veux un livre, rergarde les chapitres 2, 3, 4, 5, 6, 7, 12, 13, 15, 17 du cormen. C'est ce que j'attends qu'un informaticien sache faire en terme de calcul de complexite. Et vraiment les chapitres 2,3,4,5,6,7 au plus bas mot.

Le 06 novembre 2021 à 17:41:41 :

Le 06 novembre 2021 à 15:31:27 :
Bonjour, ce serait pour savoir si vous auriez des astuces ou des liens (cours, tutoriel) pour comprendre comment évaluer la complexité moyenne, ainsi que la complexité au pire d'un algorithme.

Par exemple si on a 2 algorithmes qui font la même tâche (ex : trier une liste ou autre chose), comment je peux savoir, en regardant l'algorithme, si ce dernier à une complexité logarithmique, linéaire, quadratique...
contexte : SpoilAfficherMasquer(On a un cours d'algorithmique à la fac, et il y a pas mal de chance qu'il y ait des questions de ce type (quel est la complexité au pire de cet algorithme ?) au partiel, mais je ne suis vraiment pas sûr de la méthode à utiliser)

Merci en tous cas !

Il n'y a qu'une seule facon de faire ca. Il faut analyser le code et compter les operations. Apres il y a des techniques d'analyse plus ou moins rafiner. Mais toutes les techniques reviennent a "il faut compter". Et il y a des techniques simple qui s'apprennent en une heure et des techniques complique qui peuvent mettre des semaines a etre compris. En principe un des but principaux d'un cours d'algo est d'apprendre comment faire cette analyse.

La technique la plus simple pour les codes base de boucles est d'estimer le pire cas du nombre d'iteration d'une execution de la boucle et tu multiplie le nombre d'iteration de la boucle par le cout au pire de ce qu'il y a dans la boucle. Et si tu as deux instructions l'une apres l'autre tu ajoute leurr cout.
Ex:

for (i=0;i<n:++i)
  sum +=i

tu fait un pire n tour de boucle. chauqe tour de boucle coute au pire 1. Ca te donne O(n)*O(1) = O(1)

for (i=0;i<n:++i)
  for (j=0; j<n; ++j)
    sum += i

Ca premiere boucle fait un pire n iteration, la deuxieme qui est imbrique fait aussi au pire n iteration, ce qu'il a dedans, coute 1. Ca donne O(n)*O(n)*O(1) = O(n^2)

for (i=0;i<n:++i)
  for (j=0; j<i; ++j)
    sum += i

Ca premiere boucle fait un pire n iteration, la deuxieme qui est imbrique fait aussi au pire i iterations, mais comme ca a l'air complique et qu'on a i<n on va compte n operations, ce qu'il a dedans, coute 1. Ca donne O(n)*O(n)*O(1) = O(n^2)

for (i=0;i<n:++i)
  if (i is prime)
    for (j=0; j<i; ++j)
      sum += i

Ca premiere boucle fait un pire n iteration, la deuxieme qui est imbrique n'est execute que si i est premier, mais comme ca a l'air complique et qu'on a i<n on va compte n operations, ce qu'il a dedans, coute 1. Ca donne O(n)*O(n)*O(1) = O(n^2)

Probablement on peut analyser ce code mieux si on sait les proprietes des nombres premiers. Mais en premiere approx c'est ca qu'on va faire. Si on sait compter le nombre de nombre premier on peut faire une analyse plus intelligente. Mais comme on utilise la notation O, l'analyse est correcte meme si il y a une analyse meilleur.

Pour faire de l'analyse en moyenne on fait pareil mais a partir d'une description probabiliste des parametres de l'algorithme et tu appliques la formule de moyenne que tu as appris en 2nde E[x]=somme pour tout x' possible P(x')*x'

Pour les algo recursif, en general tu exprimes la complexite recursivement et tu resouds la recurence. Souvent le master s'applique.

Apres ca je ne sais pas quoi te dire de plus que regardes les differente technique dans ton cours d'algo. Ou si tu veux un livre, rergarde les chapitres 2, 3, 4, 5, 6, 7, 12, 13, 15, 17 du cormen. C'est ce que j'attends qu'un informaticien sache faire en terme de calcul de complexite. Et vraiment les chapitres 2,3,4,5,6,7 au plus bas mot.

C'est exactement la méthode que je cherchais à retrouver, merci beaucoup, je vais l'analyser plus en détails !

La technique la plus simple pour les codes base de boucles est d'estimer le pire cas du nombre d'iteration d'une execution de la boucle et tu multiplie le nombre d'iteration de la boucle par le cout au pire de ce qu'il y a dans la boucle. Et si tu as deux instructions l'une apres l'autre tu ajoute leurr cout.

Je souligne quand même que c'est plus subtil que ça lorsqu'on veut la classe de complexité la plus fine possible, le paramètre maximisant le nombre de tours d'une boucle peut ne pas maximiser le nombre de tours de l'autre boucle.

Dit autrement, max f * g peut être strictement plus petit que max f * max g.

Un exemple illustratif :

Soit x un paramètre valant 0 ou 1
Soit n un paramètre entier strictement positif
Fonction f(x,n)
   Soit r = 0
   Pour i allant de i = 0 à x * (n-1)
      Pour j allant de j = 0 à (1 - x) * (n-1)
         r prend la valeur r + 1
   Retourne r

Ici chaque boucle fait au pire n tours on pourrait donc se dire que la complexité dans le pire cas est O(n) * O(n) = O(n²) ce qui est correct mais pas assez précis, l'algorithme ci-dessus est en fait en O(n) car lorsqu'une des deux boucles effectue n tours l'autre n'en effectue qu'un seul.

À noter que c'est pour ça que ça peut être plus malin de raisonner à paramètre fixé et seulement à la toute fin majorer indépendamment du paramètre. Ça évite de trop perdre en précision à cause de simplifications qui auraient pu opérer.

Le 06 novembre 2021 à 21:58:40 :

La technique la plus simple pour les codes base de boucles est d'estimer le pire cas du nombre d'iteration d'une execution de la boucle et tu multiplie le nombre d'iteration de la boucle par le cout au pire de ce qu'il y a dans la boucle. Et si tu as deux instructions l'une apres l'autre tu ajoute leurr cout.

Je souligne quand même que c'est plus subtil que ça lorsqu'on veut la classe de complexité la plus fine possible, le paramètre maximisant le nombre de tours d'une boucle peut ne pas maximiser le nombre de tours de l'autre boucle.

Dit autrement, max f * g peut être strictement plus petit que max f * max g.

Un exemple illustratif :

Soit x un paramètre valant 0 ou 1
Soit n un paramètre entier strictement positif
Fonction f(x,n)
   Soit r = 0
   Pour i allant de i = 0 à x * (n-1)
      Pour j allant de j = 0 à (1 - x) * (n-1)
         r prend la valeur r + 1
   Retourne r

Ici chaque boucle fait au pire n tours on pourrait donc se dire que la complexité dans le pire cas est O(n) * O(n) = O(n²) ce qui est correct mais pas assez précis, l'algorithme ci-dessus est en fait en O(n) car lorsqu'une des deux boucles effectue n tours l'autre n'en effectue qu'un seul.

Le 06 novembre 2021 à 22:05:00 :
À noter que c'est pour ça que ça peut être plus malin de raisonner à paramètre fixé et seulement à la toute fin majorer indépendamment du paramètre. Ça évite de trop perdre en précision à cause de simplifications qui auraient pu opérer.

Parfait, je vais prendre en compte ces remarques pour quand je commencerai à analyser des algorithmes pour m'entraîner !

En tous cas merci beaucoup pour vos explications, ça va me permettre de mieux appréhender ce type de démarche pour mes exercices et algorithmes à analyser.