辗转相除法 --- 求出两个整数的最大公约数
辗转相除法, 又名欧几里得算法(Euclidean algorithm),目的是求出两个正整数的最大公约数。它是已知最古老的算法, 其可追溯至公元前300年前。
这条算法基于一个定理:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。
有了这条定理,求出最大公约数就简单了。我们可以使用递归的方法来把问题逐步简化。
首先,我们先计算出a除以b的余数c,把问题转化成求出b和c的最大公约数;然后计算出b除以c的余数d,把问题转化成求出c和d的最大公约数;再然后计算出c除以d的余数e,把问题转化成求出d和e的最大公约数......
以此类推,逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算,直到两个数可以整除,或者其中一个数减小到1为止。
当两个整型数较大时,做a%b取模运算的性能会比较低。
更相减损术,出自于中国古代的《九章算术》,也是一种求最大公约数的算法。
他的原理更加简单:两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25,25减去10的差是15,那么10和25的最大公约数,等同于10和15的最大公约数。
比如计算10和25的最大公约数的步骤如下:
-
整数10通过移位,可以转换成求5和25的最大公约数
-
利用更相减损法,计算出25-5=20,转换成求5和20的最大公约数
-
整数20通过移位,可以转换成求5和10的最大公约数
-
整数10通过移位,可以转换成求5和5的最大公约数
-
利用更相减损法,因为两数相等,所以最大公约数是5
最后总结一下上述所有解法的时间复杂度:
1.暴力枚举法:时间复杂度是O(min(a, b)))
2.辗转相除法:时间复杂度不太好计算,可以近似为O(log(max(a, b))),但是取模运算性能较差。
3.更相减损术:避免了取模运算,但是算法性能不稳定,最坏时间复杂度为O(max(a, b)))
4.更相减损术与移位结合:不但避免了取模运算,而且算法性能稳定,时间复杂度为O(log(max(a, b)))
相关文章
- 云上持续交付实践系列1 --- java 篇
- java基础知识回顾之javaIO类---InputStreamReader和OutputStreamWriter转化流
- java基础知识回顾之---java String final类普通方法的应用之“两个字符串中最大相同的子串”
- 台大《机器学习基石》课程感受和总结---Part 1(转)
- jsp学习---使用jsp和JavaBean实现超简单网页计算器
- 深入浅出Mybatis系列(二)---配置简介(mybatis源码篇)
- HGE 系列教材(6) --- 程序流程与细节
- Atitit 团队工具链体系打造---提升团队效率的一些通用软件 attilax总结
- Atitit.自然语言处理--摘要算法---圣经章节旧约39卷概览bible overview v2 qa1.docx
- 踩坑 - 关于 “cannot be found using the classloader AntClassLoader “的解决方法 --- 已解决
- ZLMediaKit 服务器源码解读---RTSP推流拉流
- spring cloud --- Ribbon 客户端负载均衡 + RestTemplate ---心得【无熔断器】
- 深入研究Struts2(一)---Struts2是什么?它的工作原理是什么?
- 【云原生 | Kubernetes 系列】--- Zookeeper集群安装手册
- Codeforces Round #107 (Div. 2)---A. Soft Drinking
- C#比较两个对象是否为同一个对象。 Visual Studio调试器指南---多线程应用程序调试(一)
- zabbix自动化监控---自动注册机制(二十三)