Complexité temporelle de l'algorithme d'Euclide

J'ai du mal à décider quelle est la complexité temporelle du plus grand algorithme de dénominateur commun d'Euclid. Cet algorithme en pseudo-code est:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

Cela semble dépendre de a et b . Je pense que la complexité temporelle est O (a% b). Est-ce exact? Y a-t-il une meilleure façon d'écrire cela?

Une astuce pour analyser la complexité temporelle de l'algorithme d'Euclid est de suivre ce qui se passe sur deux itérations:

a', b' := a % b, b % (a % b)

Désormais, a et b diminuent tous les deux, au lieu d'un seul, ce qui facilite l'analyse. Vous pouvez le diviser en cas:

• Minuscule A: 2a <= b
• Minuscule B: 2b <= a
• Petit A: 2a > bmaisa < b
• Petit B: 2b > amaisb < a
• Égal: a == b

Maintenant, nous allons montrer que chaque cas réduit le total a+bd'au moins un quart:

• Minuscule A: b % (a % b) < aet 2a <= bdonc best diminué d'au moins la moitié, donc a+bdiminué d'au moins25%
• Minuscule B: a % b < bet 2b <= a, donc aest diminué d'au moins la moitié, donc a+bdiminué d'au moins25%
• Petit A: bdeviendra b-a, ce qui est inférieur à b/2, diminuant a+bau moins 25%.
• Petit B: adeviendra a-b, ce qui est inférieur à a/2, diminuant a+bau moins 25%.
• Égal: a+btombe à 0, ce qui diminue évidemment a+bd'au moins 25%.

Par conséquent, par analyse de cas, chaque double pas diminue a+bau moins 25%. Il y a un nombre maximum de fois que cela peut se produire avant d' a+bêtre forcé de descendre en dessous 1. Le nombre total de pas ( S) jusqu'à ce que nous atteignions 0 doit être satisfait (4/3)^S <= A+B. Maintenant, travaillez simplement:

(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)

Le nombre d'itérations est donc linéaire dans le nombre de chiffres d'entrée. Pour les nombres qui entrent dans les registres du processeur, il est raisonnable de modéliser les itérations comme prenant un temps constant et de prétendre que le temps de fonctionnement total du pgcd est linéaire.

Bien sûr, si vous avez affaire à de grands entiers, vous devez tenir compte du fait que les opérations de module à l'intérieur de chaque itération n'ont pas un coût constant. En gros, le temps d'exécution asymptotique total sera n ^ 2 fois un facteur polylogarithmique. Quelque chose comme n^2 lg(n) 2^O(log* n) . Le facteur polylogarithmique peut être évité en utilisant à la place un pgcd binaire .

La manière appropriée d'analyser un algorithme est de déterminer ses pires scénarios. Le pire cas d'Euclidean GCD se produit lorsque des paires de Fibonacci sont impliquées. void EGCD(fib[i], fib[i - 1]), où i> 0.

Par exemple, optons pour le cas où le dividende est de 55, et le diviseur est de 34 (rappelons que nous avons encore affaire à des nombres de fibonacci).

Comme vous pouvez le constater, cette opération a coûté 8 itérations (ou appels récursifs).

Essayons des nombres de Fibonacci plus grands, à savoir 121393 et ​​75025. Nous pouvons également remarquer ici qu'il a fallu 24 itérations (ou appels récursifs).

Vous pouvez également remarquer que chaque itération donne un nombre de Fibonacci. C'est pourquoi nous avons tant d'opérations. Nous ne pouvons pas obtenir des résultats similaires uniquement avec des nombres de Fibonacci.

Par conséquent, la complexité temporelle va être représentée par un petit Oh (borne supérieure), cette fois. La borne inférieure est intuitivement Omega (1): cas de 500 divisé par 2, par exemple.

Résolvons la relation de récurrence:

On peut dire alors que GCD euclidienne peut rendre le fonctionnement du journal (xy) au plus .

Il y a un bon aperçu de cela sur l' article de wikipedia .

Il a même un joli graphique de complexité pour les paires de valeurs.

Ce n'est pas O(a%b) .

On sait (voir l'article) qu'il ne prendra jamais plus de cinq fois le nombre de chiffres dans le plus petit nombre. Ainsi, le nombre maximum d'étapes augmente avec le nombre de chiffres (ln b). Le coût de chaque étape augmente également avec le nombre de chiffres, de sorte que la complexité est liée par O(ln^2 b)où b est le plus petit nombre. C'est une limite supérieure, et le temps réel est généralement inférieur.

Voir ici .

En particulier cette partie:

Lamé a montré que le nombre de pas nécessaires pour arriver au plus grand diviseur commun pour deux nombres inférieurs à n est

Il en O(log min(a, b))va de même pour une bonne borne supérieure.

Voici une compréhension intuitive de la complexité d'exécution de l'algorithme d'Euclid. Les preuves formelles sont couvertes dans divers textes tels que Introduction aux algorithmes et TAOCP Vol 2.

Pensez d'abord à ce que nous ferions si nous essayions de prendre pgcd de deux nombres de Fibonacci F (k + 1) et F (k). Vous remarquerez peut-être rapidement que l'algorithme d'Euclid effectue une itération sur F (k) et F (k-1). Autrement dit, à chaque itération, nous descendons d'un nombre dans la série de Fibonacci. Comme les nombres de Fibonacci sont O (Phi ^ k) où Phi est le nombre d'or, nous pouvons voir que le temps d'exécution de GCD était O (log n) où n = max (a, b) et log a la base de Phi. Ensuite, nous pouvons prouver que ce serait le pire des cas en observant que les nombres de Fibonacci produisent systématiquement des paires où les restes restent suffisamment grands à chaque itération et ne deviennent jamais nuls tant que vous n'êtes pas arrivé au début de la série.

Nous pouvons rendre O (log n) où n = max (a, b) lié encore plus serré. Supposons que b> = a afin que nous puissions écrire lié en O (log b). Tout d'abord, observez que GCD (ka, kb) = GCD (a, b). Comme la plus grande valeur de k est gcd (a, c), nous pouvons remplacer b par b / gcd (a, b) dans notre exécution, ce qui conduit à une borne plus étroite de O (log b / gcd (a, b)).

Le pire des cas de l'algorithme Euclide est lorsque les restes sont les plus grands possibles à chaque étape, c'est-à-dire. pour deux termes consécutifs de la séquence de Fibonacci.

Lorsque n et m sont le nombre de chiffres de a et b, en supposant n> = m, l'algorithme utilise des divisions O (m).

Notez que les complexités sont toujours données en termes de tailles d'entrées, dans ce cas le nombre de chiffres.

Le pire des cas se produira lorsque n et m sont des nombres de Fibonacci consécutifs.

pgcd (Fn, Fn − 1) = pgcd (Fn − 1, Fn − 2) = ⋯ = pgcd (F1, F0) = 1 et le nième nombre de Fibonacci est 1,618 ^ n, où 1,618 est le nombre d'or.

Donc, pour trouver gcd (n, m), le nombre d'appels récursifs sera Θ (logn).

Voici l'analyse dans le livre Data Structures and Algorithm Analysis in C de Mark Allen Weiss (deuxième édition, 2.4.4):

L'algorithme d'Euclid fonctionne en calculant continuellement les restes jusqu'à ce que 0 soit atteint. Le dernier reste différent de zéro est la réponse.

Voici le code:

unsigned int Gcd(unsigned int M, unsigned int N)
{

    unsigned int Rem;
    while (N > 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    Return M;
}

Voici un THÉORÈME que nous allons utiliser:

Si M> N, alors M mod N <M / 2.

PREUVE:

Il y a deux cas. Si N <= M / 2, alors puisque le reste est plus petit que N, le théorème est vrai pour ce cas. L'autre cas est N> M / 2. Mais alors N entre dans M une fois avec un reste M - N <M / 2, prouvant le théorème.

Ainsi, nous pouvons faire l'inférence suivante:

Variables    M      N      Rem

initial      M      N      M%N

1 iteration  N     M%N    N%(M%N)

2 iterations M%N  N%(M%N) (M%N)%(N%(M%N)) < (M%N)/2

Ainsi, après deux itérations, le reste représente au plus la moitié de sa valeur d'origine. Cela montrerait que le nombre d'itérations est au plus2logN = O(logN) .

Notez que, l'algorithme calcule Gcd (M, N), en supposant M> = N. (Si N> M, la première itération de la boucle les échange.)

Le théorème de Gabriel Lame limite le nombre d'étapes par log (1 / sqrt (5) * (a + 1/2)) - 2, où la base du log est (1 + sqrt (5)) / 2. C'est pour le pire des cas pour l'algorithme et cela se produit lorsque les entrées sont des nombres de Fibanocci consécutifs.

Une borne légèrement plus libérale est: log a, où la base du log est (sqrt (2)) est implicite par Koblitz.

À des fins cryptographiques, nous considérons généralement la complexité au niveau du bit des algorithmes, en tenant compte du fait que la taille en bits est donnée approximativement par k = loga.

Voici une analyse détaillée de la complexité bit à bit de l'algorithme Euclide:

Bien que dans la plupart des références, la complexité bit à bit de l'algorithme Euclide soit donnée par O (loga) ^ 3, il existe une borne plus étroite qui est O (loga) ^ 2.

Considérer; r0 = a, r1 = b, r0 = q1.r1 + r2. . . , ri-1 = qi.ri + ri + 1,. . . , rm-2 = qm-1.rm-1 + rm rm-1 = qm.rm

observer que: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)

et rm est le plus grand diviseur commun de a et b.

Par une affirmation dans le livre de Koblitz (Un cours de théorie des nombres et de cryptographie), on peut prouver que: ri + 1 <(ri-1) / 2 ................. ( 2)

Encore une fois dans Koblitz, le nombre d'opérations sur les bits nécessaires pour diviser un entier positif de k bits par un entier positif de 1 bits (en supposant que k> = l) est donné comme suit: (k-l + 1) .l ...... ............. (3)

Par (1) et (2) le nombre de divisions est O (loga) et donc par (3) la complexité totale est O (loga) ^ 3.

Maintenant cela peut être réduit à O (loga) ^ 2 par une remarque de Koblitz.

considérez ki = logri +1

par (1) et (2) on a: ki + 1 <= ki pour i = 0,1, ..., m-2, m-1 et ki + 2 <= (ki) -1 pour i = 0 , 1, ..., m-2

et par (3) le coût total des m divisions est borné par: SUM [(ki-1) - ((ki) -1))] * ki pour i = 0,1,2, .., m

réorganiser ceci: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Ainsi, la complexité au niveau du bit de l'algorithme d'Euclide est O (loga) ^ 2.

Pour l'algorithme itératif, cependant, nous avons:

int iterativeEGCD(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a % n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

Avec les paires de Fibonacci, il n'y a aucune différence entre iterativeEGCD()et iterativeEGCDForWorstCase()où ce dernier ressemble à ce qui suit:

int iterativeEGCDForWorstCase(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a - n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

Oui, avec les paires de Fibonacci, n = a % net n = a - nc'est exactement la même chose.

Nous savons aussi que, dans une réponse antérieure pour la même question, il y a un facteur qui prévaut en baisse: factor = m / (n % m).

Par conséquent, pour façonner la version itérative du GCD euclidien sous une forme définie, nous pouvons décrire comme un "simulateur" comme ceci:

void iterativeGCDSimulator(long long x, long long y) {
    long long i;
    double factor = x / (double)(x % y);
    int numberOfIterations = 0;
    for ( i = x * y ; i >= 1 ; i = i / factor) {
        numberOfIterations ++;
    }
    printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

Sur la base des travaux (dernière diapositive) du Dr Jauhar Ali, la boucle ci-dessus est logarithmique.

Oui, petit Oh parce que le simulateur indique le nombre d'itérations au maximum . Les paires non Fibonacci prendraient un nombre d'itérations moindre que Fibonacci, lorsqu'elles sont sondées sur GCD euclidien.

A chaque étape, il y a deux cas

b> = a / 2, alors a, b = b, a% b fera b au plus la moitié de sa valeur précédente

b <a / 2, alors a, b = b, a% b fera au plus la moitié de sa valeur précédente, puisque b est inférieur à a / 2

Ainsi, à chaque étape, l'algorithme réduira au moins un nombre à au moins la moitié de moins.

Au plus à l' étape O (log a) + O (log b) , cela sera réduit aux cas simples. Ce qui donne un algorithme O (log n), où n est la limite supérieure de a et b.

Je l'ai trouvé ici