1

次の Euclid アルゴリズムの実装を考えてみましょう。

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

ウィキペディアの優れた証明は、アルゴリズムが「常に O(h) 未満の分割を必要とすることを示しています。ここで、h は小さい数 b の桁数です」。

ただし、チューリング マシンでは、a mod b を計算する手続きの時間計算量は O(a+b) です。私の直感といくつかの大規模なテストによると、ユークリッドのアルゴリズムの複雑さは、チューリング マシンではまだ O(a+b) です。

それを証明する方法について何か考えはありますか？

4

1 に答える 1

1

チューリングマシンの2進数に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. の最後にs個のゼロビットを追加します。これが結果です。
于 2012-10-31T19:01:23.590 に答える