首页 > 代码库 > 求最大公约数的几种算法分析
求最大公约数的几种算法分析
题目——求两个整数的最大公约数
思路1、穷举算法
public static voidmain(String[] args) throws IOException { Scannerscanner = new Scanner(System.in); inta = scanner.nextInt(); intb = scanner.nextInt(); System.out.println("开始时间是"+System.currentTimeMillis()); System.out.println(gcd(a,b)); System.out.println("结束时间是"+System.currentTimeMillis()); } private static intgcd(int a, int b) { intgcd = 1; for(int i = 2; i <=a && i<=b;i++) { if(a%i == 0 && b%i == 0) { gcd= i; } } returngcd; }
验证——
用两个数字来进行验证,同时计算开始计算前的时刻和计算完毕的时刻,可以得到该算法需要的运行时间。
3450012
2100324
开始时间是1401859016757
12
结束时间是1401859016775
明显,该算法的复杂度是O(N),所需要的运行时间是18毫秒。比较长。需要改进。
思路2——改进后的穷举算法
这里假设,数字a比b大,数字a的除数不可能比a/2还大。因此,我们从a/2开始穷举找起,会更快。但是考虑到一种情况就是,数字b有可能是a的除数。所以,改进后的算法如下——
private static intgcd(int a, int b) { intgcd = 1; intm=0,n =0; //m存储较大值,n存储较小值 if(a>b){ m= a; n= b; }else{ m= b; n= a; } if(m%n == 0) { gcd= n; returngcd; } for(int i = n/2; i>=1; i--) { if(m%i == 0 && n%i == 0) { gcd= i; break; } } returngcd; }
验证——
3450012
2100324
开始时间是1401859092824
12
结束时间是1401859092834
可以看出,执行时间上明显减少了,只需要10毫秒。假如a>b,实际上这个for循环只是最多执行n/2次,比第一个完全穷举要缩短一半的时间。
尽管它的算法复杂度依然是O(N)。
但是,第二个算法只是改进了的穷举算法,效率依然不够高。比之更好些的一个算法是
思路3——进欧几里算法
这是上世纪的一个数学家进欧几里得发现的一个算法。用gcd(m,n)来表示整数m,n的最大公约数,则算法的定义为:
- 如果m%n == 0,那么gcd(m,n)就是n;
- 否则,gcd(m,n)就是gcd(n,m%n)
private static intgcd(int a, int b) { intm=0,n =0; //m存储较大值,n存储较小值 if(a>b){ m= a; n= b; }else{ m= b; n= a; } if(m%n == 0) { returnn; }else{ returngcd(n,m%n); } }
验证——
3450012
2100324
开始时间是1401858942252
12
结束时间是1401858942252
可以看到,进欧几里的算法比前两个算法快很多,执行时间在1毫秒以内。这是很不错的效率。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。