algorithm - GCDを見つけるためのブルートフォースアルゴリズムとユークリッドアルゴリズムの違い

Question

GCDを見つけるための連続整数チェックアルゴリズムがブルートフォースと見なされるのに、ユークリッドアルゴリズムはそうではないのはなぜですか? 私はそれについて混乱しています。いちいちチェックしているからでしょうか。

Answer 1

ブルート フォースアルゴリズムは、試行可能なすべての候補ソリューションを試し、どれが適合するかを確認し、その結果を回答として返します。たとえば、ブルート フォース GCD アルゴリズムは、2 つの数値のうち小さい方から開始し、 まで下降を続け1、その途中ですべての可能性を 1 つずつ調べます。

対照的に、ユークリッド アルゴリズムは 1 つずつ進むのではなく、ジャンプを行います。さらに、各ステップで GCD 問題の解となる可能性のある各数字をチェックしません。その終了条件は、現在の候補が問題の解であるかどうかをチェックするという典型的な力ずくの解法とはかなり異なります。答えが「はい」の場合は停止します。ユークリッド アルゴリズムは、別の条件、つまり をチェックして、b != 0続行するかどうかを決定します。

これらの 2 つの違い (大きなステップと異なる停止条件) により、ユークリッド アルゴリズムはブルート フォース アルゴリズムとは異なります。

Answer 2

ブルートフォース検索では、すべての (合理的な) 可能性を試します。Euclid のアルゴリズムは、これらの可能性の非常に小さなサブセットのみをチェックします。