关于欧几里德算法最坏情况的一点注记

On the Worst Case of CompIexity of Euclid's Algorithm

本文对欧几里德求两正整数最大公约数算法的时间复杂性从一个新的侧面作出了分析。结论是,若让l(m,n)表示运用欧几里德算法求任意两正整数m和n最大公约数时的迭代次数,则l(m,n)≤log_2(m·n)(假定m和n不都为1)。

Taking a new approach, we have analysed the time complexity of Euchd's algorithm for computing the greatest common divisor of two positive integers The conctusion is: Let l(m, n) denote the numbet of iterations of execution of Euclid's algorithm upon input data m and n. Then l(m, n)<log; (m.n), provided that not both m and n are l's.