哪种方法可以提供更好的时间复杂度来找到给定数字的 GCD(a,b)？
质因数分解
(或)
下面的方法
int gcd(int a, int b)
{
return (b==0)?a:gcd(b,a%b);
}
最佳答案
这取决于您输入的范围以及您对 Prime factorization 的实现. 由于后者没有针对大数的有效算法，因此似乎可以实现 GCD 以提供更有效的结果。
要点是如何在您的算法中计算模 - 假设它被有效地实现(不使用除法)，这个 GCD 的实现(也称为 Euclidean algorithm)应该更有效。
关于algorithm - 哪种方法更好，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24796688/