Eŭklida algoritmo: Malsamoj inter versioj

e
→‎Rultempo: plibonigadeto, anstataŭigis: |thumb| → |eta| per AWB
[nekontrolita versio][nekontrolita versio]
e (Roboto: anstataŭigo de "Ŝablono:El" per "Ŝablono:EL" (laŭ VP:AA))
e (→‎Rultempo: plibonigadeto, anstataŭigis: |thumb| → |eta| per AWB)
== Rultempo ==
 
[[Dosiero:Euclidean algorithm running time X Y.png|thumbeta|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 sinsekvaj [[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]]).
23 504

redaktoj