Eŭklida algoritmo: Malsamoj inter versioj

"sufiĉes"->"sufiĉas" "sinsekbvaj"->"sinsekvaj"
[nekontrolita versio][nekontrolita versio]
e (roboto aldono de: ar, bg, ca, cs, de, el, en, es, fi, fr, hu, id, it, ja, ko, lt, lv, nds, nl, no, pl, pt, ro, simple, sl, sr, sv, tr, uk, vi, zh)
("sufiĉes"->"sufiĉas" "sinsekbvaj"->"sinsekvaj")
Simile, se ''d'' estas dividanto de ''b'' kaj ''r'' do ''d'' estas dividanto de ''a''.
 
La pli supraj rezonadoj veras por ĉiu dividanto ''d''. Tial, la plej granda komuna divizoro de ''a'' kaj ''b'' estas ankaŭ la plej granda komuna divizoro de ''b'' kaj ''r''. Pro tio estas sufiĉessufiĉas daŭrigi serĉadon por la plej granda komuna divizoro kun la nombroj ''b'' kaj ''r''.
 
Pro tio ke ''r'' estas pli malgranda je absoluta valoro ol ''b'', estos atingita ''r=0'' post ne pli ol ''b'' ŝtupoj.
[[Dosiero:Euclidean algorithm running time X Y.png|thumb|230px|Grafika prezento de la [[rultempo]] por PGKD (x, y). Ruĝa indikas rapidan kalkuladon, pli blua indikas pli malrapidan kalkuladon.]]
 
Por eŭklida algoritmo, la enigoj postulantaj la plej multajn dividojn estas du sinsekbvajsinsekvaj [[fibonaĉi-nombro]]j, ĉar iliaj kvocientoj estas la plej malrapida [[konverĝa (ĉenfrakcio)|konverĝa]] [[ĉenfrakcio]] de la [[ora proporcio]]. Ĉi tiu la plej malbona okazo postulas ''[[Granda O|O]](n)'' dividojn, kie ''n'' estas kvanto de ciferoj en la enigo. Tamen, la divido mem ne estas operacio de [[konstanta tempo]], tiel la tuta [[tempa komplikeco]] de la algoritmo estas ''O(n<sup>2</sup>)'' ([[kvadrata tempo]]).
 
La kaŭzo estas ke divido de du ''n''-bitaj nombroj prenas tempon ''O(n(m+1))'', kie ''m'' estas la longo de la kvociento. Konsideru la kalkuladon de ''PGKD (a, b)'' kie ''a'' kaj ''b'' havi maksimume ''n'' bitojn, estu <math>a_0,\dots,a_k</math> la vico de nombroj produktitaj per la algoritmo, kaj estu <math>n_0,\dots,n_k</math> iliaj longoj. Tiam ''k=O(n)'', kaj la rultempo estas barita per
201 405

redaktoj