更相相减和辗转算法比较有意思，以前我还没见过这两算法，学习了。。。

我也觉得不是  对这类比较我暂时还不会  只能凭个人感觉……
假设输入的同样两个数
第一种和第二种方法的操作都有两个：比较和赋值
而操作的次数取决于输入的参数
不会算……：应该说一二  两种算法的时间效率是一样的
第三种算法的基本操作是赋值 操作次数取决于较小数
前三种在最好情况下算法的时间效率应该是一样的
第四种怎么看都是最差的


哪位知道的请详细解答一下啊……

有时间再看

2虽然是除法，但是执行次数比1少很多。
比如1,1000000
1要减100W次
2只需要一次1%1000000，然后一次1000000%1就只剩下1了，最多两次。

[[it] 本帖最后由 风居住的街道 于 2008-11-11 15:51 编辑 [/it]]

//
这不是我想知道的


请你把辗转相除的  平均操作次数用数学公式表达出来
并指出它的增长次数

拜托，这是你的帖子好不好？这种工作似乎应该楼主来做吧？

是的啊 因为我不会啊……

对于辗转相除    我觉得不能用一般的解决方式来解决
应该用  散点图  或者 计数  来观察
但这样得出来的结果似乎不能让人满意  

就像我猜测它应该是对数阶的一样

http://zhidao.baidu.com/question/11300492.html

某些时候，百度是很强大的……

还有这个：
一个快速的二进制多重精度gcd算法A Fast Algorithm for Computing gcd ...
求两个整数的最大公因子(gcd)的经典的Euclid算法时间复杂度为O(In3n),不适宜于多重精度运算.论文证明了gcd的相关性质,提出了一个基于二进制的、适用于多重精度运算的 ...
scholar. - 类似网页

还有这个：
http://zh.

[[it] 本帖最后由 风居住的街道 于 2008-11-11 17:49 编辑 [/it]]

//那个一个公式不能说明什么东西
递归解决最大公约数问题的确不需要额外的空间和时间
递归的增长次数应该和辗转相除的增长次数是一样的
但是最起码得有一个递推公式吧？？
我是不知道怎么写的

|k=[lgM](向上取整) (N为底)  
|m(0)=1
|m（k）=m(k-1)+1
|
反向替换 =>m(k)=m(k-i)+i
i换成k-1   =>m(k)=m(1)+k-1=k
k换成 [lgM]
m(n)=[lgM]∈O(lgn)

第一次  推这东西
不知道可对

[[it] 本帖最后由 liyanhong 于 2008-11-11 18:30 编辑 [/it]]