Niveau Master

Complexité algorithmique

Posté par
denyro 27-09-16 à 20:10

Bonjour la communauté,
J'ai des difficultés avec la compréhension de "Complexité  algorithmique".
Pouvez-vous svp m'apporté un coup de pousse avec le TD ci-dessous.
Merci d'avance

Un entier n peut donc être représenté par un tableau T à deux entrées. Le premier champ de la i ^ème position (T [ i,1]) contient a i et le deuxième (T[i, 2]) contient b_i.
Soient T ₁ et T ₂ les tableaux représentant deux entiers n 1 et n 2 . On note taille₁ et taille₂ les tailles des tableaux T 1 et T 2 ( par rapport à la première entrée).

Soit la fonction PGCD suivante :

fonction PGCD ( T 1 , T 2 : tableau) : entier
       pgcd, p1, p2 : entier
       pgcd = 1 ; p1 = 1 ; p2=1

     tant que (p1 ≤ taille ₁ ) et (p2 ≤ taille₂ ) faire
              si T₁[p1,1] = T₂ [p2,1] alors
                      m=min (T₁ [p1,2], T₂ [p2,2])
                      pgcd=pgcd [T 1 [p1,1]]^m

                      p1=p1 + 1
                      p2=p2 + 1
                     sinon
                              si T₁[p1,1] < T₂ [p2,1] alors
                                  p1 = p1 + 1
                           sinon
                                     p2 = p2 + 1
                           fin si
                      fin si
          fin tant que
          retourner (pgcd)

Déterminer la complexité temporelle de la fonction PGCD.

Posté par re : Complexité algorithmique 27-09-16 à 20:24

Bonsoir,
je ne comprends pas la représentation des entiers, ni l'instruction pgcd=pgcd [T 1 [p1,1]]^m.

Mais on peut dire que, dans le pire des cas, si il est possible, la boucle tantque est parcourue taille₁taille₂ fois.

Posté par re : Complexité algorithmique 27-09-16 à 20:26

Ps : on dit un coup de pouce, du moins me semble t-il.

Posté par re : Complexité algorithmique 27-09-16 à 20:55

verdurin @ 27-09-2016 à 20:24

Bonsoir,
je ne comprends pas la représentation des entiers, ni l'instruction pgcd=pgcd [T 1 [p1,1]]^m.

Mais on peut dire que, dans le pire des cas, si il est possible, la boucle tantque est parcourue taille₁

taille₂ fois.

Merci Verdurin pour la promptitude.
Effectivement c'est "Coup de pouce" merci pour la remarque.

Quant à l'instruction, c'est un produit.
J'avais omis le "x" durant la saisie.

pgcd=pgcd x [T 1 [p1,1]]

Posté par re : Complexité algorithmique 27-09-16 à 22:11

Je vais tenter un peu de divination.

Ma boule de cristal me dit que l'entier n est représenté par un tableau où la première ligne contient les facteurs premiers de n et la seconde leurs exposants.

$n=\prod_{i=1}^{\text{taille}}T[1,i]^{T[2,i]}$

A t-elle raison ?

Si c'est le cas, je dirais que le temps d'exécution est un O(ln(n₁)ln(n₂))

Mais sans garantie.

Posté par re : Complexité algorithmique 28-09-16 à 15:16

bonjour verdurin,
Pourquoi ta mesure de complexité temporelle dépend-elle de n1 et n2 ? alors qu'il me semble que c'est la taille des tableaux qui comptent.
Si l'on considère qu'il y a k opérations ( affectations+ tests) à chaque passage et que dans le pire des cas il y a taille1 x taille2 passages donc kx taille1xtaille2 opérations ( et je ne compte pas les élévations à une puissance, c'est peut-être un tort). comment alors mesures-tu la complexité temporelle?

Posté par re : Complexité algorithmique 28-09-16 à 17:20

Bonjour,
avec des amis on a trouvé Taille₁ + Taille₂

Je vois que du bleu. lol

Posté par re : Complexité algorithmique 28-09-16 à 19:22

bonjour,
Regarde comment fonctionne l'algo sur les deux nombres suivants:

$p_i$ est le ième nombre premier

$n_1=(\prod_{i\le 1000}p_i) \times p_{1001}^m \times p_{2001}$

$n_2=p_{1001}^m\times (\prod_{1002\le i\le 2000}p_i)$