在排序数组上计算 GCD

Question

如果数组被排序，是否有可能对用于获取数组中数字 gcd 的任何算法进行一些优化？ 谢谢！

Answer 1

那么，让我们看看。查找数字数组的 GCD 的一般方法是：

result = a[0]
for i = 1 to length(a)-1
result = gcd(result, a[i])

那么 gcd 算法的复杂性是什么？嗯，这是一个相当复杂的问题。例如，参见欧几里得算法的时间复杂度

如果我们假装，正如公认的答案中所假设的那样，GCD算法是恒定时间(即O(1))，那么上述循环的复杂性是O(n)。对于适合计算机寄存器的数字，这是一个合理的假设。如果是这样的话，那么花费 O(n log n) 时间对数组进行排序几乎肯定会是失败者。

但实际上，GCD 计算在两个数字中的位数上是线性的。如果您的输入数据由大量大数字组成，则首先对数组进行排序可能会给您带来优势。原因是，根据定义，gcd(a, b)的结果会给你一个不大于min(a,b)的数字。因此，通过首先获取两个最小数字的 GCD，您可以限制必须处理的位数。这种限制是否会克服对数组进行排序的成本尚不清楚。

如果数字大于计算机寄存器(数百位)，则GCD计算成本更高。但话又说回来，排序也是如此。

因此，您的问题的答案是，排序几乎肯定会提高计算数字数组GCD的速度，但性能改进是否会抵消排序成本尚不清楚。

我认为您确定的唯一方法是使用代表性数据对其进行测试。