欧几里得算法的时间复杂度

Question

119

我很难确定欧几里得算法的时间复杂度。这个伪代码如下：

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

看起来这取决于a和b。我认为时间复杂度为O(a%b)。这正确吗？有更好的写法吗？

- Donald T

16

请参阅Knuth TAOCP第2卷，他提供了广泛的覆盖范围。只是顺带一提，有几个小贴士：答案与a%b不成比例。最坏情况是当a和b是相邻的斐波那契数时。 - Jerry Coffin

3

@JerryCoffin 注意：如果您想以更正式的方式证明最坏情况确实是斐波那契数列，可以考虑使用数学归纳法证明终止前的第n步必须至少与gcd乘以第n个斐波那契数相同。 - Mygod

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cs guy · Answer 1

在每一步中，都有两种情况

如果 b >= a / 2，则执行 a, b = b, a % b 将使 b 的值最多减少一半

如果 b < a / 2，则执行 a, b = b, a % b 将使 a 的值最多减少一半，因为此时 b 小于 a / 2

因此，在每一步中，该算法至少会将一个数字减少至少一半。

在最多 O(log a)+O(log b) 步骤中，这将被简化为简单的情况。这将产生一个 O(log n) 的算法，其中 n 是 a 和 b 的上限。

我在这里找到了它