【Java】O記法について

O記法とは

O記法とは、アルゴリズムの計算量を評価するための指標です。
この計算量が、従前に触れた「処理速度・メモリ使用量」に大きく関わってきます。
したがって、計算量の見積もりは重要になってきます。この計算量の見積もりの事を計算量導出と言います。
計算量導出は、基本的に、最悪なケースを想定しておけばよいです。最悪なケースとは、計算量が一番多くなってしまった時のことです。

計算量導出について

• 問題1：要素数nの数列aに整数iは含まれているか？
  アルゴリズム：線形探索
  最悪：一番最後に含まれているか、もしくは、含まれていないケース
  導出：n回となるので、O(n)と表記

• 問題2：要素数nの数列aと要素数mの数列bに重複する要素はあるか？
  アルゴリズム：2重ループでaの全要素とbの全要素のペアをチェック
  最悪：一番最後に重複しているか、もしくは、重複する要素がないケース
  導出：n × m回となるので、O(nm)と表記

• 問題3：要素数nの数列aと要素数mの数列bに重複する要素はあるか？
  条件：数列aの要素数nは、0以上10未満
  アルゴリズム：サイズ10の配列sをFalseで初期化し、配列aの全ての要素αについて、s[α]をTrueにする。そして、配列bのある要素βについて、s[β]がTrueなら重複ありと判断
  最悪：一番最後に重複しているか、もしくは、重複する要素がないケース
  導出：n + mとなるので、O(n+m)と表記

この問題3のコード例と解説については、後述します。

O記法のルール

O記法で求めたい計算量導出はざっくりしたもので良いので、下記のルールがあります。

1. 最高次数の項以外を無視
2. 定数係数を無視

下記の関数を例にして、ルールを当てはめます。

$$6n^3+10n^2+4n$$

「1.最高次数の項以外を無視」のルールを当てはめます。

$$6n^3$$

「2.定数係数を無視」のルールを当てはめます。

$$n^3$$

最終的な表記は、下記のようになります。

$$O(n^3)$$

基本演算数

log n	n	n^2	n^3
6	100	10,000	1,000,000
9	1,000	1,000,000	1,000,000,000

上記のように、nが100→1,000になる10倍になったら、
log nは、3増えるだけ、
nの2乗は、100倍になり、
nの3乗は、1,000倍になります。

実行環境等にもよりますが、1秒間で処理できる演算の回数は1億回（10の8乗回）が目安であると覚えておいてください。

問題3のコード例

問題3について、具体的なコードは下記の通りとなります。

public class Main {
    public static void main(String[] args) {
        // 前提条件の設定
        // 数列aとbの要素数を設定
        int n = 3;
        int m = 4;

        // 数列aとbを初期化
        int[] a = {1, 3, 4}; // 数列a
        int[] b = {9, 7, 5, 4}; // 数列b

        // アルゴリズム
        // サイズ10の配列sをFalseで初期化
        boolean[] s = new boolean[10];

        // 数列aの全ての要素a[i]について、s[a[i]]をTrueにする
        for (int i = 0; i < n; i++) {
            s[a[i]] = true;
        }

        // 数列bのある要素b[i]について、S[b[i]]がTrueになれば重複ありと判定
        boolean hasDuplicate = false;
        for (int i = 0; i < m; i++) {
            if (s[b[i]]) {
                hasDuplicate = true;
                break;
            }
        }

        // 結果を出力
        if (hasDuplicate) {
            System.out.println("数列aと数列bに重複する要素があります");
        } else {
            System.out.println("数列aと数列bに重複する要素はありません");
        }
    }
}

コード例の解説

このコードは、前提条件の設定とアルゴリズムに分けられます。

前提条件

int n = 3;
int m = 4;

int[] a = {1, 3, 4};
int[] b = {9, 7, 5, 4};

1. 数列aのサイズnを3で初期化します。
2. 数列bのサイズmを4で初期化します。
3. 数列aの要素を1, 3, 4で初期化します。
4. 数列bの要素を9, 7, 5, 4で初期化します。

アルゴリズム

boolean[] s = new boolean[10];

for (int i = 0; i < n; i++) {
    s[a[i]] = true;
}

boolean hasDuplicate = false;
for (int i = 0; i < m; i++) {
    if (s[b[i]]) {
        hasDuplicate = true;
        break;
    }
}

if (hasDuplicate) {
    System.out.println("数列aと数列bに重複する要素があります");
} else {
    System.out.println("数列aと数列bに重複する要素はありません");
}

1. サイズ10の配列sの全要素をfalseで初期化します。

   sの状態:[false, false, false, false, false, false, false, false, false, false]

2. n回ループするfor文を定義して、
3. 配列aの全ての要素a[i]について、s[a[i]]をtrueにします。

   以下、2.と3.のコードの流れ（計算量導出3回）
   s[a[0]] → s[1] → 配列sのインデックス1をtrueにします。
   s[a[1]] → s[3] → 配列sのインデックス3をtrueにします。
   s[a[2]] → s[4] → 配列sのインデックス4をtrueにします。
   sの状態:[false, true, false, true, true, false, false, false, false, false]

4. 変数hasDuplicateをfalseで初期化します。（Duplicateの和訳は重複）
5. m回ループするfor文を定義して、
6. 条件式がs[b[i]]というif文を定義して、
7. s[b[i]]がtrueなら、変数hasDuplicateをtrueに更新します。
8. そして、強制的にfor文を抜けます。

   以下、5.～8.のコードの流れ（計算量導出4回）
   s[b[0]] → s[9] → 配列sのインデックス9確認します。falseなのでif文の条件式を満たしません。
   s[b[1]] → s[7] → 配列sのインデックス7確認します。falseなのでif文の条件式を満たしません。
   s[b[2]] → s[5] → 配列sのインデックス5確認します。falseなのでif文の条件式を満たしません。
   s[b[3]] → s[4] → 配列sのインデックス4確認します。trueなのでif文の条件式を満たすので、変数hasDuplicateをtrueに更新して、強制的にfor文を抜けます。

9. 条件式が変数hasDuplicateというif文を定義して、
10. 条件式がtrueなら、数列aと数列bに重複する要素がありますと出力します。
11. 条件式がfalseなら、
12. 数列aと数列bに重複する要素はありませんと出力します。

以上により、計算量導出はnの3回とmの4回で合計はn + mの7回となりました。