algorithm - 哪种方法更好

Question

哪种方法可以提供更好的时间复杂度来找到给定数字的 GCD(a,b)？

质因数分解

(或)

下面的方法

int gcd(int a, int b)
{
    return (b==0)?a:gcd(b,a%b);
}

Answer 1

这取决于您输入的范围以及您对 Prime factorization 的实现.由于后者没有针对大数的有效算法，因此似乎可以实现 GCD 以提供更有效的结果。

要点是如何在您的算法中计算模 - 假设它被有效地实现(不使用除法)，这个 GCD 的实现(也称为 Euclidean algorithm)应该更有效。