Eŭklida algoritmo: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
KuBOT (diskuto | kontribuoj) e Roboto: anstataŭigo de "Ŝablono:El" per "Ŝablono:EL" (laŭ VP:AA) |
e →Rultempo: plibonigadeto, anstataŭigis: |thumb| → |eta| per AWB |
||
Linio 109:
== Rultempo ==
[[Dosiero:Euclidean algorithm running time X Y.png|
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]]).
| |||