アルゴリズム入門

コンピュータは計算が速く、何でもこなせるというイメージがありますが、実際には、複雑で膨大なデータを処理する際、すべてを一瞬で解決するわけではありません。そんなとき、効率的な解決策として登場するのが『アルゴリズム』です。アルゴリズムは、限られたリソースで最適な結果を得るための道筋を示すもので、プログラミングの基礎でありながら非常に奥深いテーマです。本記事では、アルゴリズムの基本的な仕組みや考え方をわかりやすく解説します。

*対数表記は log_a(M) とします

アルゴリズムとは

アルゴリズムとは、「問題を解くための手順や計算方法」を指す言葉です。例えば、1から100までの整数を全て足す問題を考えてみましょう。

1~100の整数和計算

アルゴリズム例１：1つずつ足していく

最も単純な方法は「1+1=3」「3+3=6」「6+4=10」「10+5=15」・・・と1つずつ足していく方法です。この方法では、このような足し算を99回繰り返して答えを導きます。おそらく計算が得意な人でも5分以上はかかるでしょう。

アルゴリズム例２：式変形を行い一気に計算する

1~100までの数は「1と100」「2と99」「3と98」・・・「50と51」というように、「合計が101になる50個のペア」に分解することができます。これより求める答えは、「101×50 = 5050」と導けます。

アルゴリズム例１では99回の計算が必要でしたが、アルゴリズム例２では「101×50」の1回で済みます。よって、例２の方が効率の良いアルゴリズムであると言えます。
現代のコンピュータは人間よりも格段に速く計算を行うことができますが、それにも限界があります。計算量が膨大になれば簡単にコンピュータの計算速度の限界を超えてしまいます。より少ない計算量で同じ結果を得るために、アルゴリズムの考え方を学んでいくことが大切です。

アルゴリズムの基本構造

アルゴリズムは、問題を解決するための一連の手順やルールの集まりですが、その基本的な構造は主に3つの要素で構成されます。それは、「順次処理」、「分岐」、「繰り返し」です。これらの制御構造を理解することで、アルゴリズムがどのように機能し、どのように効率的な計算を実現するかが見えてきます。

1. 順次処理
   指示された手順を一つずつ順番に実行していく最も基本的な処理方法です。例えば、料理のレシピに従うときのように、指示された手順に従って一つ一つの操作を実行していきます。順次処理はアルゴリズムの基礎であり、プログラムの中で最もシンプルな処理です。
2. 分岐
   条件に応じて異なる処理を実行する構造です。プログラムの中で「もし～ならば」といった条件文に対応し、特定の条件が満たされるかどうかによって次の動作が決まります。例えば、ある数が正の数か負の数かによって異なる処理を行う場合が典型です。分岐によってアルゴリズムは柔軟性を持ち、様々な条件に応じた解決策を導き出すことができます。
3. 繰り返し
   同じ操作を複数回実行する構造で、ループとも呼ばれます。ループは特定の条件が満たされるまで、または指定回数だけ処理を繰り返します。例えば、リスト内の全ての要素を処理するアルゴリズムでは、繰り返し処理が不可欠です。繰り返し処理は、大量のデータを効率よく処理する際に非常に重要な役割を果たします。

これら3つの構造は、ほぼすべてのアルゴリズムに共通して見られる基本要素です。アルゴリズムを理解する際には、この順次処理、分岐、繰り返しという基礎的な枠組みを把握することが不可欠です。この理解が、より複雑なアルゴリズムを設計・解析する際の土台となります。

計算量表記

アルゴリズムの効率性を評価するためには、ビッグオー記法（Big-O Notation）という方法がよく使われます。ビッグオー記法は、アルゴリズムの処理に要する時間やメモリ量が、入力データの増加に伴ってどのように変化するかを表すものです。以下がその代表的な例です。

• O(1)
  入力データのサイズに関わらず、常に一定の時間で処理が完了する。
• O(N)
  処理時間が入力データのサイズに比例して増加する。
  例：N個の要素を1つずつ処理する場合
• O(N^2)
  入力データのサイズが増えると、処理時間がその二乗に比例して増加する。
  例：二重ループなど
• O(log N)
  処理時間が入力データのサイズに対して対数的に増加する。
  例：二分探索など

代表的なアルゴリズムの例

素数判定法

自然数Nが素数であるかどうかを判定する問題

アルゴリズム例１：単純な素数判定法

例として53が素数であるかを判定してみます。ここでは単純に2から10までで割り切れるものがないかを一つづつ調べていく方法を考えます。

53 ÷ 2 = 26…1
53 ÷ 3 = 17…2
53 ÷ 4 = 13…1
・
・
・
53 ÷ 50 = 1…3
53 ÷ 51 = 1…2
53 ÷ 52 = 1…1
→ どれでも割り切れない → 素数

上記のように 53 が素数だとわかりましたが、計算に時間がかかってしまいます。

一般の整数Nについても、同じように2からN-1まで割り切れるかどうかを調べることで、素数判定を行うことが可能です。しかし、計算量はO(N)と遅く、例えばこの方法で 10^12 + 39 が素数かどうかを調べると、家庭用コンピュータでも計算に10分以上を要します。

code1

public static boolean isprime(long N) {
　// Nを2以上の整数とし、Nが素数であればtrue, 素数でなければfalseを返す
　for(long i = 2; i <= N-1; i++) {
　　//Nがiで割り切れた場合、この時点で素数ではないとわかる
　　if(N % i == 0) return false;
  }
　return true;
}

アルゴリズム例２：高速な素数判定法

実は 2 から N-1 まで調べる必要はなく、「√N」まで調べて割り切れなければ素数だと判定できます。逆に全ての合成数（2以上の自然数で、素数ではない数）は2以上√N以下のいずれかの整数で割り切れます。例えば先ほど例に出した 53 であれば、√53 = 7.28… なので2, 3, 4, 5, 6, 7 までで割り切れなければ「53は素数」と判定できます。

53 ÷ 2 = 26…1
53 ÷ 3 = 17…2
53 ÷ 4 = 13…1
53 ÷ 5 = 10…3
53 ÷ 6 =   8…5
53 ÷ 7 =   7…4
→ どれでも割り切れない → 素数

このアルゴリズムの計算量は O(√N) であり、例１の方法と比べて格段に効率的です。例えば、例１では10分以上かかる 10^12 + 39 の計算時間はわずか0.01秒ほどです。

code2

public static boolean isprime(long N) {
　// Nを2以上の整数とし、Nが素数であればtrue, 素数でなければfalseを返す
　for(long i = 2; i * i <= N; i++) {
　　//Nがiで割り切れた場合、この時点で素数ではないとわかる
　　if(N % i == 0) return false;
  }
　return true;
}

このアルゴリズムの正当性は、背理法を用いて証明することができます。
以下がその証明です。

---

事実F：Nが合成数であれば2以上√N以下の約数が存在する

事実Fが成り立たないと仮定する.
すなわち, Nが合成数であり, 1以外で最小のNの約数Aが√Nを超えていると仮定する.
約数の性質より, A×B = N となる正の整数Bが存在する. このとき B は N の約数である.
A×B = N より B = N/A < √N である. これは2以上の最小の約数がAであることに矛盾する.
よって, 仮定は成り立たず, 事実Fは正しい.

Q.E.D.

---

ソートアルゴリズム：選択ソートとマージソート

ソートアルゴリズムは、データを順序通りに並べるための手法であり、様々な方法が存在します。ここでは、比較的簡単で直感的な「選択ソート」と、効率的で広く使用される「マージソート」の2つのソートアルゴリズムについて解説します。

選択ソート（Selection Sort）

選択ソートは、リストを繰り返しスキャンし、最小または最大の要素を見つけて、未ソート部分の先頭と交換するソートアルゴリズムです。これをリスト全体がソートされるまで繰り返します。

1. 最小値の検索：リスト内で最小の要素を見つける
2. 交換：最小の要素をリストの先頭の未ソート部分と交換する
3. 繰り返し：未ソート部分の次に進み、再度最小の要素を探し、交換を行う
4. 終了：リスト全体がソートされるまで続ける

例：配列[64, 25, 12, 22, 11]のソート

1. 1回目のスキャンで最小値 11 を見つけ、先頭と交換 → [11, 25, 12, 22, 64]
2. 次に、[25, 12, 22, 64] の中から最小値 12 を見つけ、交換 → [11, 12, 25, 22, 64]
3. このプロセスを繰り返してソート

計算量の見積もり

N個の数の中から最小値を見つけるにはN-1回の比較が必要です。2回目以降も、N-2回、N-3回・・・、2回、1回と続きます。そこで1からNまでの整数の総和は N(N+1)/2 なので、合計比較回数は
(N-1) + (N-2) + … + 2 + 1 = N(N-1)/2
となり、このアルゴリズムの計算量はO(N^2)と言えます。

code3

public static void selectionSort() {
   Scanner scanner = new Scanner(System.in);

   // 入力
   System.out.println("入力：");
   int N = scanner.nextInt();
   int[] A = new int[N + 1]; // 配列のサイズはN+1

   for (int i = 1; i <= N - 1; i++) {
       System.out.println("A[" + i + "]の要素を入力：");
       A[i] = scanner.nextInt();
   }

   // 選択ソート
   for (int i = 1; i <= N - 1; i++) {
       int min = i;
       int minValue = A[i];
       for (int j = i + 1; j <= N; j++) {
           if (A[j] < minValue) {
               min = j;
               minValue = A[j];
           }
       }
       // swap
       int temp = A[i];
       A[i] = A[min];
       A[min] = temp;
   }

   // 出力
   for (int i = 1; i <= N; i++) {
       System.out.println(A[i]);
   }
   scanner.close();
}

マージソート（Merge Sort）

マージソートは、分割統治法に基づくソートアルゴリズムです。リストを分割し、各部分をソートした後、再度マージ（統合）することで全体をソートします。マージソートでは、2つのソート済み配列を合併するMerge操作が基礎になっています。

Merge操作

1. 列Cを用意する（列Cは空）
2. 以下の操作を、列A（ソート済み）・列B（ソート済み）の全ての要素が消えるまで繰り返す
   1. 列Aが空であれば、列Bで最小の要素を列Cに移す
   2. 列Bが空であれば、列Aで最小の要素を列Cに移す
   3. どちらでもなければ、列Aで残っている最小の要素と、列Bで残っている最小の要素を比較し、小さい方を列Cに移す

例：列A[13, 34, 50, 75]、列B[11, 20, 28, 62]の場合

1. 1. 13 と 11 を比較 → 11を列Cに移動
      列C[11]
   2. 13 と 20 を比較 → 13を列Cに移動
      列C[11, 13]
   3. 34 と 20 を比較 → 20を列Cに移動
      列C[11, 13, 20]
   4. 34 と 28 を比較 → 28を列Cに移動
      列C[11, 13, 20, 28]
   5. 34 と 62 を比較 → 34を列Cに移動
      列C[11, 13, 20, 28, 34]
   6. 50 と 62 を比較 → 50を列Cに移動
      列C[11, 13, 20, 28, 34, 50]
   7. 75 と 62 を比較 → 62を列Cに移動
      列C[11, 13, 20, 28, 34, 50, 62]
   8. 75 を列Cに移動
      列C[11, 13, 20, 28, 34, 50, 62, 75]

それでは、Merge操作を利用して配列をソートしてみます。マージソートは、分割統治法を利用した次のようなアルゴリズムです。

1. k個の要素からなる列を、それぞれk/2個の要素からなる列A・列Bに分割
2. 列Aに対してマージソートを行い、ソートした後の列を列A’とする
3. 列Bに対してマージソートを行い、ソートした後の列を列B’とする
4. 列A’と列B’に対してMerge操作を行うことで、k個の要素からなる列がソートされる

例：配列[31, 41, 59, 26]のソート

1. [31, 41]と[59, 26]に分割
2. [31, 41]をソートし、[31, 41]となる
3. [59, 26]をソートし、[26, 59]となる
4. [31, 41]と[26, 59]に対してMerge操作を行い、[26, 31, 41, 59]が得られる

計算量の見積もり

Merge操作を行うと列の長さが倍になるため、合併の段階はおよそlog_2(N)個です。各段階における比較回数はN回以内であるため、全体の比較回数はO(N log_(N))回となります。

code4

public static void mergeSortMain(int[] A) {
   int N = A.length;

   mergeSort(A, 0, N);
   for (int i = 0; i < N; i++) {
       System.out.println(A[i]);
   }
}

// A[l], A[l+1], ..., A[r-1]を小さい順に整列する関数
public static void mergeSort(int[] A, int l, int r) {
   if (r - l <= 1) return; // 要素が1つまたは0個の場合はソート不要

   int m = (l + r) / 2;
   mergeSort(A, l, m);
   mergeSort(A, m, r);

   // マージ操作
   merge(A, l, m, r);
}

private static void merge(int[] A, int l, int m, int r) {
   int[] left = new int[m - l];
   int[] right = new int[r - m];

   // 配列のコピー
   System.arraycopy(A, l, left, 0, left.length);
   System.arraycopy(A, m, right, 0, right.length);

   int i = 0, j = 0, k = l;

   // マージ処理
   while (i < left.length && j < right.length) {
       if (left[i] <= right[j]) {
           A[k++] = left[i++];
       } else {
           A[k++] = right[j++];
       }
   }

   // 残りの要素をコピー
   while (i < left.length) {
       A[k++] = left[i++];
   }

   while (j < right.length) {
       A[k++] = right[j++];
   }
}

まとめ

アルゴリズムは、問題解決のための効率的な手順を示すもので、コンピュータ科学の中心的なテーマです。順次処理、分岐、繰り返しといった基本構造を理解することで、アルゴリズムの動作原理を把握することができます。また、アルゴリズムの効率性は、ビッグオー記法を用いて評価され、計算量に応じて処理速度が異なります。最適なアルゴリズムを選択することが、限られたリソースで迅速かつ正確な結果を得る鍵となります。