我很难确定欧几里得算法的时间复杂度。这个伪代码如下:
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
看起来这取决于a和b。我认为时间复杂度为O(a%b)。这正确吗?有更好的写法吗?
我很难确定欧几里得算法的时间复杂度。这个伪代码如下:
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
看起来这取决于a和b。我认为时间复杂度为O(a%b)。这正确吗?有更好的写法吗?
在每一步中,都有两种情况
如果 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 的上限。
我在这里找到了它
a%b
不成比例。最坏情况是当a
和b
是相邻的斐波那契数时。 - Jerry Coffin