[解決済み] ユークリッド・アルゴリズムの時間計算量

質問

ユークリッドの最大公約数アルゴリズムの時間計算量がどの程度か判断に迷っています。このアルゴリズムを擬似コードで表すと

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

に依存しているようです。 a と b . 私の考えでは、時間の複雑さはO(a % b)です。これは正しいのでしょうか？もっと良い書き方があるのでしょうか？

どのように解決するのですか？

ユークリッドのアルゴリズムの時間複雑性を分析する一つのコツは、2回の繰り返しで何が起こるかを追うことです。

a', b' := a % b, b % (a % b)

これでaとbが片方だけでなく両方減ることになり、解析がしやすくなりました。ケースに分けることができます。

• 小さなA 2a <= b
• タイニーB 2b <= a
• スモールA 2a > b しかし a < b
• スモールB 2b > a しかし b < a
• イコール a == b

今度は、すべてのケースで合計が減少することを示します。 a+b を少なくとも 4 分の 1 減少させることを示します。

• タイニーA b % (a % b) < a そして 2a <= b というように b は少なくとも半分に減少するので a+b は少なくとも 25%
• タイニーB a % b < b そして 2b <= a というように a は少なくとも半分に減少するので a+b は少なくとも 25%
• 小さいA b になります。 b-a よりも小さい。 b/2 を減少させる a+b を少なくとも 25% .
• スモールB a になります。 a-b よりも小さい。 a/2 を減少させる a+b を少なくとも 25% .
• イコール a+b に低下します。 0 となり、明らかに減少しています。 a+b を少なくとも 25% .

したがって、ケース分析によって、すべてのダブルステップが減少します。 a+b を少なくとも 25% . この現象が起きる回数には上限があります。 a+b を下回るよう強制されます。 1 . 総ステップ数( S ) を満たす必要があります。 (4/3)^S <= A+B . あとはそれを実行するだけです。

(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)

つまり、反復処理の回数は入力桁数に対して線形になります。CPUのレジスタに収まるような数であれば、反復に一定の時間がかかるとモデル化して 合計 の実行時間は線形であるかのように装います。

もちろん、大きな整数を扱う場合は、各反復内のモジュラス演算が一定のコストではないという事実を考慮する必要があります。大雑把に言うと、漸近的な実行時間の合計は n^2 x ポリロガス係数になります。 のような n^2 lg(n) 2^O(log* n) . ポリロガス的な要素を避けるには、代わりに バイナリgcd .