1. 概要

この短いチュートリアルでは、ユークリッドのアルゴリズムの2つの一般的な解釈を見て、それらの時間計算量を分析します。

2. 最大公約数

ユークリッドの互除法は、2つの整数の最大公約数を計算するための方法です。

2つの整数の最大公約数は、両方の数を余りゼロで除算する最大数であることを思い出してみましょう。 整数との最大公約数を表すために使用します。 したがって、たとえば：

  • 、ここで、は正の整数です

このような小さな数の場合、この作業は簡単に思えるかもしれませんが、数が増えるにつれてますます困難になります。 したがって、説得力が必要な場合は、計算してみてください。

ユークリッドのアルゴリズムは、このプロセスを非常に簡単にすることができます。 このアルゴリズムにはいくつかのバリエーションがありますが、それぞれは最終的に、アレクサンダーのユークリッドが彼の作品Elementsで提示した提案から導き出されています。

今日は、2つの一般的なものについて説明します。

3. 減算によるユークリッドのアルゴリズム

ユークリッド原論の命題2に示されているユークリッドのアルゴリズムの元のバージョンは、減算を採用しています。

一部の正の整数とについては、小さい方の数を大きい方の数から等しくなるまで繰り返し減算することで機能します。この時点で、いずれかの項の値が入力の最大公約数です。

3.1. アルゴリズム

このアルゴリズムは、ほんの数ステップで定義できます。

ステップ1：の場合、の値を返しますステップ2：それ以外の場合は、そのままにしてステップ1に戻りますステップ3：それ以外の場合は、ステップ1に戻ります

それでは、例としてこのアルゴリズムをステップスルーしてみましょう。

に到達しました。これは、を意味します。

3.2. 擬似コード

このアルゴリズムを擬似コードで表すこともできます。

3.3. 時間計算量

の合計を考えることにより、アルゴリズムの最悪の場合の時間計算量を推定できます。 基本ケースを除外すると、この合計は各再帰ステップで減少します。各ステップの可能な最小の控除は1であり、すべての正の整数は1の公約数を持つことが保証されているため、時間計算量は次のようになります。 。の上限

4. 除算によるユークリッドの互除法

ユークリッドのアルゴリズムの最新の適応では、除算を使用して2つの整数との最大公約数を計算します。ここで、はです。 これは、いくつかの重要な観察に基づいています。

  • は、任意の正の整数の場合

この最初の観察は非常に直感的ですが、2番目の観察はそれほど明白ではありません。その証拠を調べたい場合は、これらのスライドを確認してください。

これらの観察を念頭に置いて、私たちのアルゴリズムは単に次の割り当てを繰り返します。

ゼロになるまで。 この時点で、の最終値から結果を簡単に取得できます。

4.1. アルゴリズム

除算によるユークリッドのアルゴリズムには、次の3つのステップがあります。

ステップ1：の場合、の値を返しますステップ2：それ以外の場合は、余りを除算して変数に格納しますステップ3：、、、および手順1に戻ります

入力のアルゴリズムをステップスルーしてみましょう：

に到達したので、それを知っています。

4.2. 擬似コード

このアルゴリズムを再帰関数として実装できます。

または、whileループを使用して、同じ動作をキャプチャすることもできます。

4.3. 時間計算量

2つの入力が連続するフィボナッチ数である場合、アルゴリズムが実行するステップ数が最大化されることがわかります。

より具体的には、ステップとが必要な場合、との可能な最小値はそれぞれとです。 これは誘導によって証明することができます。

したがって、手順が必要な場合：

次に、、は「黄金比」であり、に等しいことを思い出してください。 次に、それを推測できます。

最後に、次のことを解くことができます。

したがって、ステップ数は常に、より少なくなります。ここで、は2つの入力値のうち小さい方です。 したがって、はアルゴリズムの最悪の場合のコストの上限です。

アルゴリズムの2番目の引数として入力する必要がないことは注目に値します。 つまり、whereを実行できます。 この場合、アルゴリズムは最初に1つの追加ステップを実行するだけで、値を効果的に交換します。 なぜそうなるのか考えてみてください…いつの結果はどうなるのでしょうか？ この追加の手順により一定の時間が追加されるため、最悪の場合の境界は影響を受けません。

5. 結論

この記事では、ユークリッドの互除法の2つのバリエーションを実装して、2つの正の整数の最大公約数を見つけました。 次に、各ソリューションの複雑さを分析しました。