complexity-theory - 图灵机上欧几里得最大公约数算法的复杂性

Question

考虑 Euclid 算法的这种实现：

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

维基百科上的一个很好的证明表明，该算法“总是需要少于 O(h) 的除法，其中 h 是较小数字 b 中的位数”。

然而，在图灵机上，计算 mod b 的过程的时间复杂度为 O(a+b)。我的直觉和一些大型测试告诉我，欧几里德算法的复杂度在图灵机上仍然是 O(a+b)。

关于如何证明这一点的任何想法？

Answer 1

如果我在图灵机上对二进制数实现 GCD，我将实现以下算法。我看不出它会比 O((ln a + ln b)^2) 小多少。我认为最有效的表示方法是在第 2 步之后按位交错两个值。

1. 令 s1 = a 的最低有效位中的零数。删除这些底部 s1 零位。
2. 令 s2 = b 的最低有效位中的零数。删除这些底部 s2 零位。
3. 让 s = min(s1,s2)
4. 现在 a 和 b 都是奇数。如果 b < a 则交换 a 和 b。
5. b >= a。设置 b = b - a，然后从 b 中删除所有最低有效零位。
6. 如果 b != 0，转到 4。
7. 在 a 的末尾添加 s 个零位。这就是结果。