辗转相除法与更相减损术的区别？

两者本质是否相同？效率不同？

青铜星玩家

百度移动游戏玩家均可认证(限百度账号),去领取

活动截止:2100-01-01

去徽章馆》

woc

p吧眼熟诶

更相减损术本质就是辗转相除

更相减损效率低

本质相同，更相减损实际上就是辗转相除

详情请见数学必修三。运算量可能大不少

@圣梦星辉，从本质上就可以看出，辗转相除法是用除法，也就是减去N个最小数，明显比更相减损法效率大了很多。比较小的数无法体现，但是一旦数大了就明显了

钩直饵咸，经验拿好

这个不得不承认。原理是一样的，但是老外的辗转相除法比中国的更相减损法先进。明显辗转相除法效率高不是一点点。如果数字相差大，老外运行一步，中国的要多运行N步。减法怎么能跟得上除法的脚步。所以按照科学理论，辗转相除法是最终的方案，更相减损法是辗转相除法的半成品，最后一步和积没有完成。

别逗我了，你以为老祖宗想不到？等你做除法再取余，天都亮了，明明更相减损法是拿来做除数优化，方便快速求解的，比如中途只需要减一次，就可以马上除个2或者3，三两下就出来了，特别适合人做复杂口算。体现在代码里就是gcd的二进制优化，明明有时候俩奇数一减就可以去掉好多2因数，做余数的慢的要死还不一定能减掉n次，建议你们这些小朋友多读点书。

其实die码效率上来说还是辗转相除法更快。
但是两个最坏情况都是O(log n)的
不过一般用辗转相除法，好写。只有高精度运算的时候采用更相减损术

都是 $O(n\log n)$ 的罢

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

12回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六