求助:辗转相除法的算法复杂度
有两个自然数,m和n(其中n<m),用辗转相除法求其最大公约数,过程如下:
假设m=49,n=28.
先用其中的较大数49除以较小数28,余数为21(第一次运算).
然后用28除以刚才得到的余数21,得到余数为7(第二次运算).
再用21除以7,余数为0,得到结论-----7是49和28的最大公约数(第三次运算).
现在我要问的问题是:对于任意的m和n,最不利情况下,要进行多少次运算才能得到结果?
为更进一步说明,我举另外一种算法:
假设m=49,n=28.
先用其中的较大数49除以较小数28,余数不为0(第一次运算).
然后分别用49和28除以27,不能同时整除(第二次运算).
再分别用49和28除以26,不能整除(第三次运算).
...........................
当分别用49和28除以7时,能同时整除(第n次运算).
这种方法最不利的情况是两个数互质情况,将运行n遍(n为m和n中的较小数)
[ 本帖最后由 物理大腕 于 2007-9-13 12:55 编辑 ]
