112

Euclid の最大公約数アルゴリズムの時間計算量を判断するのに苦労しています。疑似コードでのこのアルゴリズムは次のとおりです。

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

aとbに依存しているようです。私の考えでは、時間の計算量は O(a % b) です。あれは正しいですか？それを書くためのより良い方法はありますか？

4

11 に答える 11

83

ユークリッドのアルゴリズムの時間計算量を分析するための 1 つのトリックは、2 回の反復で何が起こるかを追跡することです。

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

これで、a と b が 1 つだけではなく両方減少するため、分析が容易になります。ケースに分けることができます：

  • 小さなA:2a <= b
  • 小さなB:2b <= a
  • 小A：2a > bしかしa < b
  • 小B：2b > aでもb < a
  • 同等：a == b

ここで、ケースごとに合計a+bが少なくとも 4 分の 1減少することを示します。

  • Tiny A:b % (a % b) < aと2a <= b、だからb少なくとも半分にa+b減少するので、少なくとも減少する25%
  • Tiny B:a % b < bと2b <= a、だからa少なくとも半分にa+b減少するので、少なくとも25%
  • 小 A:bになりb-a、これは 未満で、少なくともb/2減少します。a+b25%
  • 小 B:aになりa-b、これは 未満で、少なくともa/2減少します。a+b25%
  • 等しい:a+bに低下します0。これは明らかa+bに少なくとも 減少してい25%ます。

したがって、ケース分析によると、すべてのダブルステップa+bは少なくとも25%. a+bが強制的に を下回る前に、これが発生する最大回数があります1。S0 に達するまでの合計ステップ数 ( ) は、 を満たす必要があり(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 レジスタに収まる数値については、反復を一定の時間がかかるものとしてモデル化し、gcdの合計実行時間が線形であると仮定するのが合理的です。

もちろん、大きな整数を扱っている場合は、各反復内の剰余演算のコストが一定ではないという事実を考慮する必要があります。大まかに言えば、総漸近実行時間は、多対数係数の n^2 倍になります。のようなもの n^2 lg(n) 2^O(log* n)。代わりにバイナリ gcdを使用することで、多重対数係数を回避できます。

于 2010-10-20T18:20:18.280 に答える
32

アルゴリズムを分析する適切な方法は、最悪のシナリオを判断することです。ユークリッド GCD の最悪のケースは、フィボナッチ ペアが関与する場合に発生します。 void EGCD(fib[i], fib[i - 1])、ここで i > 0。

たとえば、被除数が 55 で除数が 34 の場合を考えてみましょう (まだフィボナッチ数を扱っていることを思い出してください)。

ここに画像の説明を入力

お気づきかもしれませんが、この操作には 8 回の反復 (または再帰呼び出し) が必要でした。

より大きなフィボナッチ数、つまり 121393 と 75025 を試してみましょう。ここでも、24 回の反復 (または再帰呼び出し) が必要であることがわかります。

ここに画像の説明を入力

また、各反復でフィボナッチ数が得られることにも気付くでしょう。そのため、私たちは非常に多くの操作を行っています。さすがにフィボナッチ数だけでは似たような結果は得られません。

したがって、今回は、時間計算量は小さな Oh (上限) で表されます。下限は直感的に Omega(1) です。たとえば、500 を 2 で割った場合です。

再帰関係を解いてみましょう:

ここに画像の説明を入力

その場合、ユークリッド GCD で log(xy) 操作ができるのはせいぜいと言えます。

于 2014-03-01T09:02:55.480 に答える
19

ウィキペディアの記事でこれをよく見てください。

値のペアの複雑さの素晴らしいプロットもあります。

そうではありませんO(a%b)。

小さい方の桁数の 5 倍を超えるステップを実行することは決してないことが知られています (記事を参照)。したがって、ステップの最大数は桁数として増加します(ln b)。各ステップのコストも桁数に応じて増加するため、複雑さはO(ln^2 b)b が小さい数によって制限されます。これは上限であり、実際の時間は通常これより短くなります。

于 2010-10-20T17:00:47.223 に答える
15

ここを参照してください。

特にこの部分：

Lamé は、n より小さい 2 つの数の最大公約数に到達するために必要なステップ数は次のとおりであることを示しました。

代替テキスト

O(log min(a, b))良い上限も同様です。

于 2010-10-20T17:15:21.537 に答える
9

Euclid のアルゴリズムの実行時の複雑さを直感的に理解できます。形式的な証明は、Introduction to Algorithms や TAOCP Vol 2 などのさまざまなテキストでカバーされています。

まず、2 つのフィボナッチ数 F(k+1) と F(k) の gcd を取得しようとするとどうなるか考えてみてください。ユークリッドのアルゴリズムが F(k) と F(k-1) を反復することがすぐにわかるかもしれません。つまり、反復ごとに、フィボナッチ数列の数値が 1 つ下に移動します。フィボナッチ数は O(Phi ^ k) で、Phi は黄金比であるため、GCD の実行時間は O(log n) で、n=max(a, b) であり、log は Phi の底を持つことがわかります。次に、フィボナッチ数が各反復で剰余が十分に大きいペアを一貫して生成し、シリーズの最初に到達するまでゼロにならないことを観察することにより、これが最悪のケースであることを証明できます。

O(log n) where n=max(a, b) bound をさらにきつくすることができます。b >= a と仮定すると、bound at O(log b) と書くことができます。まず、GCD(ka, kb) = GCD(a, b) であることに注意してください。k の最大値は gcd(a,c) であるため、実行時に b を b/gcd(a,b) に置き換えることができ、O(log b/gcd(a,b)) のより厳密な境界につながります。

于 2015-06-06T21:30:35.060 に答える
4

Euclid Algorithm の最悪のケースは、残りが各ステップで可能な最大の場合です。フィボナッチ数列の 2 つの連続する用語。

n と m が a と b の桁数である場合、n >= m と仮定すると、アルゴリズムは O(m) 分割を使用します。

複雑さは常に入力のサイズ(この場合は桁数) で表されることに注意してください。

于 2010-10-20T17:21:25.927 に答える
4

n と m の両方が連続するフィボナッチ数である場合、最悪のケースが発生します。

gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)=⋯=gcd(F1,F0)=1 で、n 番目のフィボナッチ数は 1.618^n で、1.618 は黄金比です。

したがって、gcd(n,m) を見つけるには、再帰呼び出しの回数は Θ(logn) になります。

于 2018-01-12T13:36:01.100 に答える
1

ただし、反復アルゴリズムの場合は次のようになります。

int iterativeEGCD(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a % n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

フィボナッチ ペアでは、後者が次のように見える場所との間iterativeEGCD()に違いはありません。iterativeEGCDForWorstCase()

int iterativeEGCDForWorstCase(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a - n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

はい、フィボナッチ ペアn = a % nとn = a - n、まったく同じことです。

また、同じ質問に対する以前の回答では、一般的な減少要因があることもわかっていますfactor = m / (n % m)。

したがって、ユークリッド GCD の反復バージョンを定義された形式で形作るために、次のような「シミュレーター」として表すことができます。

void iterativeGCDSimulator(long long x, long long y) {
    long long i;
    double factor = x / (double)(x % y);
    int numberOfIterations = 0;
    for ( i = x * y ; i >= 1 ; i = i / factor) {
        numberOfIterations ++;
    }
    printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

Dr. Jauhar Aliの研究(最後のスライド) に基づいて、上記のループは対数です。

ここに画像の説明を入力

はい、小さいです。シミュレーターは最大で反復回数を通知するためです。非フィボナッチ ペアは、ユークリッド GCD で調べた場合、フィボナッチよりも反復回数が少なくなります。

于 2014-03-01T21:54:59.977 に答える