我最近一直在求解a 问题 找到两个数字的，使用递归。我想到的第一个解决方案就是下面给出的。
long long gcd(long long a, long long b){
if(!(a - b) return a;
return gcd(max(a, b) - min(a, b), min(a, b));
}
我看到了其他人的解决方案，一种方法非常普遍，这就是下面的类似。
long long gcd(long long a, long long b){
if(!b) return a;
return gcd(b, a % b);
}
这两个程序的时间复杂性之间的差异是什么？我如何优化前一个解决方案，我们怎么能说后一种解决方案比任何其他算法都有效？
I have been recently solving a problem to find GCD/HCF of two numbers using Recursion. The first solution that came to my mind was something like given below.
long long gcd(long long a, long long b){
if(!(a - b) return a;
return gcd(max(a, b) - min(a, b), min(a, b));
}
I saw other people's solutions and one approach was very common which was something like given below.
long long gcd(long long a, long long b){
if(!b) return a;
return gcd(b, a % b);
}
What is the difference between the Time Complexities of these two programs? How can I optimise the former solution and how can we say that the latter solution is efficient than any other algorithm?
发布评论
评论（1）
如果您谈论的是时间复杂性，那么您应该考虑使用Big-O符号。第一个算法是
o（n），第二个算法是o（logn），其中n = max（a，b）。实际上，第二个算法是对第一个算法的优化。在第一个解决方案中，如果
a和b之间的差距很大，则需要许多减去a -b到达其余a％b。因此，我们可以通过使用整数模拟操作来改进该部分，从而得出第二个算法。If you are talking about the time complexity, then you should consider the big-O notation. The first algorithm is
O(n)and the second one isO(logn), wheren = max(a, b).In fact, the second algorithm is a straigtforord optimization of the first one. In the first solution, if the gap between
aandbis huge, it takes many subtractions fora - bto reach the remaindera % b. So we can improve this part by using the integer modulo operation instead, which yields the second algorithm.