0

中期的にアルゴリズムクラスを紹介する準備をしているときに、教授が投稿した以前のテストをいくつか試しましたが、次の質問が見つかりました。

gcd（312,455）を2つの方法で計算します。各数値の因数分解を見つける方法と、ユークリッドのアルゴリズムを使用する方法です。各アプローチの複雑さは何ですか？

彼の答えは：

gcd(455,312) = gcd(312,143) = gcd(143,26) = gcd(26,13) = gcd(13,0) = 13

factors(312)= {2, 3, 13} factors(455)= {5, 7, 13}

複雑さ：

  • gcd-log(n)
  • 要因-sqrt(n)

彼はどのようにして複雑さに到達したのですか？

4

2 に答える 2

1

ユークリッド GCD を分析するには、最悪の場合の値を選択する必要があります。個人的には、フィボナッチ ペアがこの問題に最も適していることがわかりました。例えば

EGCD(121393, 75025) = 1; // With 24 iterations (or recursive calls).

この「シーケンス」を見てください。

ここに画像の説明を入力

フィボナッチ ペアでは、次のことがわかります。

121393 % 75025 == 121393 - 75025 == 46368.

したがって、 の減少要因があります。121393 / 46368 = **2.61** (more or less);

間違いなく、最悪の場合の実行時間は Small Oh Notation を使用します。これは、たとえば、被除数が 1000 で除数が 2 の場合、最良の場合は Omega(1)、つまり定数時間がかかるためです。

減少因子があるので、次のような再帰関係を置くことができます。

ここに画像の説明を入力

この実行時間は、EGCD アルゴリズムの反復バージョンとまったく同じ方法で適用できることに注意する必要があります。

于 2014-03-01T20:29:55.040 に答える
0

与えられた複雑さは、必要な算術演算の数に対する大まかな最悪の場合の境界です。

  • ユークリッド アルゴリズム: where がa >= bあるため、最大で 2 つのリダクション ステップの後、少なくとも最初のオペランドが によってリダクションされます。したがって、リダクション ステップの数は、一定の定数の対数に制限されます。gcd(a,b) = gcd(b, a mod b)min(b, a mod b) < a/21/2asqrt(2)c * log(a)c

  • 因数分解: 数の素数性をテストするか、素数の 2 乗を因数分解するには、数の平方根までの因数をチェックするだけで十分です。与えられた数の因数が小さい場合、割り切れるテストはさらに少なくて済みます。したがって、必要な分割数は によって簡単に制限されsqrt(a)+sqrt(b)ます。ld(a)最大でも の因数が存在する可能性があるため、gcd を取得するための残りの比較と乗算も によって拘束されaます。ld(a) < sqrt(a)sqrt(a)

于 2013-02-16T19:39:15.543 に答える