Complexité temporelle de l'algorithme d'Euclide

Question

J'ai de la difficulté à décider de 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 ça?

Answer 1

L'astuce pour l'analyse de la complexité temporelle de l'algorithme d'Euclide est de suivre ce qui se passe sur deux itérations:

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

Maintenant a et b réduira à la fois, au lieu d'un seul, ce qui rend l'analyse plus facile. Vous pouvez le diviser en cas:

• Minuscule A: 2*a <= b
• Minuscule B: 2*b <= a
• Petit Un: 2*a > b a < b
• Petit B: 2*b > a, mais b < a
• L'égalité: a == b

Montrer que chaque cas diminue a+b pour un montant minimum:

• Minuscule A: b % a % b) < a et 2*a <= b, alors b est diminué au moins de moitié, donc a+b a diminué d'au moins 25%
• Minuscule B: a % b < b et 2*b <= a, donc a est diminué au moins de moitié, donc a+b a diminué d'au moins 25%
• Petit A: b devient b-a, qui est inférieure à b/2, la diminution de a+b par au moins 25%.
• Petit B: une volonté de devenir un b, ce qui est inférieur à a/2, la diminution de a+b par au moins 25%.
• L'égalité: a+b tombe à 0, ce qui est évidemment la diminution de a+b par au moins 25%.

Par conséquent, par l'analyse de cas, chaque double-étape diminue a+b par au moins 25%. De sorte que le nombre total d'étapes (S) jusqu'à ce que nous avons atteint 0 doit satisfaire 1.25^S <= A+B. Maintenant, juste la travailler:

(5/4)^S <= A+B
S <= lg[5/4](A+B)
S is O(lg[5/4](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)

Donc, parce que le nombre d'itérations est linéaire en la taille de saisie, et le temps total d'exécution est linéaire en le nombre d'itérations (en supposant que le mod prend constante de temps), le temps total d'exécution est linéaire en la taille de saisie.

Answer 2

La façon d'analyser un algorithme est par la détermination de son pire des scénarios. Euclidienne, PGCD dans le pire des cas se produit lorsque Fibonacci Paires sont impliqués. void EGCD(fib[i], fib[i - 1]), où j'ai > 0.

Par exemple, nous allons opter pour le cas où le dividende est de 55 ans, et le diviseur est de 34 (rappelons que nous sommes toujours aux prises avec les nombres de fibonacci).

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

Essayons de plus grands nombres de Fibonacci, à savoir 121393 et 75025. On peut remarquer ici qu'il a fallu 24 itérations (ou les appels récursifs).

Vous pouvez également remarquer que chaque itérations donne un nombre de Fibonacci. C'est pourquoi nous avons beaucoup d'opérations. Nous ne pouvons pas obtenir les mêmes résultats qu'avec la suite de Fibonacci en effet.

Par conséquent, la complexité du temps va être représentée par de petits Oh (limite supérieure), cette fois. La limite inférieure est intuitivement Omega(1): cas de l'500 divisé par 2, par exemple.

Nous allons résoudre la relation de récurrence:

Nous pouvons donc dire que Euclidienne, PGCD peut faire log(xy) de l'opération au plus.

Answer 3

Il y a un grand coup d'oeil sur l' article de wikipedia.

Il a même une belle parcelle de complexité pour les paires de valeurs.

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

Il est connu (voir l'article) qu'il ne sera jamais à prendre des mesures plus de cinq fois le nombre de chiffres dans le nombre plus petit. Ainsi, le nombre maximum d'étapes croît à mesure que le nombre de chiffres (ln b). Le coût de chaque étape augmente aussi le nombre de chiffres, de sorte que la complexité est liée par O(ln^2 b) où b est le plus petit nubmer. C'est une limite supérieure, et le temps réel est généralement moins.

Answer 4

Voir ici

En particulier cette partie:

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

Donc, O(log min(a, b)) est une bonne limite supérieure.

Answer 5

Le pire cas de l’algorithme d’Euclide est celui où les restes sont les plus grands possibles à chaque étape, c’est-à-dire. pendant 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 que n> = m, l'algorithme utilise des divisions O (m).

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