图灵机上欧几里得最大公约数算法的复杂性 [英] The complexity of Euclid's greatest common divisor algorithm on a Turing Machine

问题描述

考虑Euclid算法的这种实现:

Consider this implementation of Euclid's algorithm:

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

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

A nice proof on wikipedia shows that the algorithm "always needs less than O(h) divisions, where h is the number of digits in the smaller number b".

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

However, on a Turing Machine a procedure that computes a mod b has a time complexity of O(a+b). My intuition and some large tests tell me that the complexity for Euclid's algorithm is still O(a+b) on a Turing Machine.

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

Any thoughts on how to prove that?

推荐答案

如果我要在Turing机器上的二进制数字上实现GCD，我将实现以下算法.我看不到它会比O((ln a + ln b)^ 2)小.我认为，最有效的表示方法是在步骤2之后按位交织两个值.

If I were implementing GCD on binary numbers on a Turing machine, I'd implement the following algorithm. I can't see how it would be smaller than O((ln a + ln b)^2) though. The most efficient representation I think would be bitwise interleaving both values after step 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个零位.这就是结果.

这篇关于图灵机上欧几里得最大公约数算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！