プログラムを繰り返し処理する際、手順数が爆発的に増えると、計算が追い付かなくなり、PCが止まってしまうので、アルゴリズムの手順数の把握が必要となります。

目次

ビッグオー表記について
具体的なアルゴリズムについて
ビッグオー記法によるアルゴリズムの手順数
アルゴリズムのコード例
アルゴリズム実施結果

ビッグオー表記について

アルゴリズムの手順数を測る方法に、ビッグオー表記が用いられます。

ビッグオー表記とは？

アルゴリズムの手順数を示す関数
$
　　f(n), g(n)(n∈\mathbf{N})
$
に対して
$
　　lim_{n→∞}f(n)/g(n)<∞
$
となるとき、
$
　　f(n) = O(g(n))
$
と書き、
$
　　O(g(n))
$
をビッグオー表記といいます。
（注：ビッグオー表記の他にスモールオー表記($o(g(n))$)というのもあります）

ここで、
　　$f(n)$：調査したいアルゴリズム
　　$g(n)$：基準となるアルゴリズム
とすると、$f(n)$のアルゴリズムの手順数がおおまかに把握ができます。
ここで、
　　$g(n)$として、$1、log(n)、n、nlog(n)、n^2、a^n、n！$
等がよく使用されており、
　　$f(n) = O(g(n))$であれば、$f(n)$は$g(n)$と同等か、$g(n)$
より効率の良いアルゴリズムと認識されます。

具体的なアルゴリズムについて

定数時間（$O(1)$）:
例：ランダム取得

対数時間（$O(log(N))$）:
例：二分探索

線形時間（$O(N)$）:
例：線形探索

線形対数時間（$Nlog(N)$）:
例：マージソート

二次時間（$O(N^2)$）:
例：二重ループ、バブルソート

三次時間（$O(N^3)$）:
例：三重ループ

指数時間（$O(2^N)$）:
例：部分集合の抽出

階乗時間（$O(N!)$）:
例：巡回セールスマン問題、行列式の定義による計算

ビッグオー記法によるアルゴリズムの手順数

	10個のデータ (N=10)	100個のデータ (N=100)	1,000個のデータ (N=1,000)	10,000個のデータ (N=10,000)
$O(1)$	1	1	1	1
$O(log(N))$	約3	約7	約10	約13
$O(N)$	10	100	1000	10000
$O(Nlog(N))$	約30	約700	約10000	約130000
$O(N^2)$	100	10000	1000000	100000000
$O(2^N)$	1024	1267650600228229401496703205376	約$10^{301}$	約$10^{3010}*10^{0.3}$
$O(O(N!))$	3628800	93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000	非常に大きい数	非常に大きい数

アルゴリズムのコード例

アルゴリズム動作コード

import java.util.*;
import java.util.Scanner;
import java.text.SimpleDateFormat;
import java.util.Date;

class Main{
	//アルゴリズム数
	private static int algorithmDataCount = [アルゴリズム数(N)];
    private static int innerNestCount = [ネストの回数(M)];
	
	//アルゴリズム確認リスト
	private static List<Integer> numArray = new ArrayList<Integer>();
	private static Integer makeListElement(int i){
        //アルゴリズムを調査する配列を設定
		return Integer.valueOf(algorithmDataCount - i);
	}
	private static void makeArray(){
    	for(int i=0; i<algorithmDataCount; i++){
    		numArray.add(makeListElement(i));
    	}
	}

    public static void main(String[] args){
    	Main.makeArray();
    	long startTime = System.currentTimeMillis();
    	System.out.println("-------------------------");
    	System.out.println("アルゴリズム数: " + algorithmDataCount);
    
        System.out.println("----アルゴリズム開始----");
        //調査したいアルゴリズムをコメントアウト
        //System.out.println("O(1)のアルゴリズム例：ランダム取得");
    	//TestO1Algorithm.o1Algorithm(numArray);
    	//System.out.println("O(logN)のアルゴリズム例：二分探索");
    	//TestOlognAlgorithm.olognAlgorithm(numArray, algorithmDataCount);
    	//System.out.println("O(N)のアルゴリズム例：線形探索");
       	//TestOnAlgorithm.onAlgorithm(numArray, algorithmDataCount);
    	//System.out.println("O(NlogN)のアルゴリズム例：マージソート");
    	//TestOnlognAlgorithm.onlognAlgorithm(numArray, 0, algorithmDataCount - 1);
    	//System.out.println("O(N^M)のアルゴリズム例：M重ループ");
    	//TestOpownmAlgorithm.onpowernAlgorithm(numArray, algorithmDataCount, innerNestCount);
    	//System.out.println("O(2^N)のアルゴリズ	ム例：部分集合を全て取得");
    	//TestOpow2nAlgorithm.opow2nAlgorithm(numArray);
    	//System.out.println("O(N!)のアルゴリズム例：要素の全順列を生成");
    	//TestOfactrialnAlgorithm.ofactrialnAlgorithm(numArray, 0);
        System.out.println("----アルゴリズム終了----");
    	System.out.println("-------------------------");
    	long endTime = System.currentTimeMillis();
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy/MM/dd hh:mm:ss");
        System.out.println("開始時刻：" + (sdf.format(new Date(startTime))));
        System.out.println("終了時刻：" + (sdf.format(new Date(endTime))));
        System.out.println("処理時間：" + (endTime - startTime) + " ミリ秒");
    }
}

定数時間（O(1)）

class TestO1Algorithm {
	//O(1)のアルゴリズム例：ランダム取得
    public static void o1Algorithm(List<Integer> numArray) {
    	Random random = new Random();
    	int randomInt = random.nextInt(numArray.size());
        int argorithmCount = 1;
    	System.out.println("N=" + argorithmCount + " 選択されたランダム値: " + numArray.get(randomInt) + " ## ランダムインデックス: " + randomInt);
    }
}

対数時間（O(log(N))）

class TestOlognAlgorithm {
 	//O(log(N))のアルゴリズム例：二分探索
    public static void olognAlgorithm(List<Integer> numArray, int algorithmDataCount) {
    	Random random = new Random();
    	int randomInt = random.nextInt(algorithmDataCount);
        int argorithmCount = 1;
    	int max = algorithmDataCount - 1;
		int min = 0;
		while(true) {
			int mid = (max + min) / 2;
			if (mid < randomInt) {
				min = mid;
				System.out.println("N=" + argorithmCount + " 最小ランダムインデックス < 最大ランダムインデックス : " + min + " < " + max);
			} else {
				max = mid;
				System.out.println("N=" + argorithmCount + " 最小ランダムインデックス < 最大ランダムインデックス : " + min + " < " + max);
			}

			if (max - min <= 1) {
				System.out.println("N=" + argorithmCount + " 選択されたランダム値: " +  numArray.get(randomInt) + " ## ランダムインデックス: " + randomInt);
				break;
			}
            argorithmCount++;
		}
    }
}

線形時間（O(N)）

class TestOnAlgorithm {
    //O(N)のアルゴリズム例：線形探索
    public static void onAlgorithm(List<Integer> numArray, int algorithmDataCount) {
    	Random random = new Random();
    	int randomInt = random.nextInt(algorithmDataCount);
		for(int argorithmCount=1; argorithmCount<algorithmDataCount+1; argorithmCount++){
			if(argorithmCount == randomInt){
				System.out.println("N=" + argorithmCount + " 選択されたランダム値: " + numArray.get(randomInt) + " ランダムインデックス: " + randomInt);
				break;
			}else{
				System.out.println("N=" + argorithmCount + " 選択されたランダム値ではりません");
			}
    	}
    }
}

線形対数時間（Nlog(N)）

class TestOnlognAlgorithm {
    //O(Nlog(N))のアルゴリズム例：マージソート
    private static int argorithmCount = 1;
    public static void onlognAlgorithm(List<Integer> numArray, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            onlognAlgorithm(numArray, left, mid);
            onlognAlgorithm(numArray, mid + 1, right);
            merge(numArray, left, mid, right);
        }
    }

    public static void merge(List<Integer> numArray, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        List<Integer> L = new ArrayList<>(numArray.subList(left, mid + 1));
        List<Integer> R = new ArrayList<>(numArray.subList(mid + 1, right + 1));
        
        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L.get(i) <= R.get(j)) {
                numArray.set(k++, L.get(i++));
                System.out.println("N=" + TestOnlognAlgorithm.argorithmCount + " ソート中");
            } else {
                numArray.set(k++, R.get(j++));
                System.out.println("N=" + TestOnlognAlgorithm.argorithmCount + " ソート中");
            }
            TestOnlognAlgorithm.argorithmCount++;
        }

        while (i < n1) {
            numArray.set(k++, L.get(i++));
            System.out.println("N=" + TestOnlognAlgorithm.argorithmCount + " ソート中");
            TestOnlognAlgorithm.argorithmCount++;
        }

        while (j < n2) {
            numArray.set(k++, R.get(j++));
            System.out.println("N=" + TestOnlognAlgorithm.argorithmCount + " ソート中");
            TestOnlognAlgorithm.argorithmCount++;
        }
    	System.out.println("ソート結果： " + numArray);
    }
}

M次時間（O(N^M)）

class TestOpownmAlgorithm {
	//O(N^M)のアルゴリズム例：M重ループ
    private static int argorithmCount = 1;
	public static int onpowernAlgorithm(List<Integer> numArray, int algorithmDataCount, int innerNest){
		String loopNumWord = "重ループ";
		int loopNum = 1;
		for(int i = 0; i<innerNest; i++){
			loopNum = i + 1;
		}
		loopNumWord = loopNum + loopNumWord;
		if(innerNest <= 0) {
			return 0;
		}else{
			innerNest -= 1;
		}
		for (int i=0; i<algorithmDataCount; i++) {
			System.out.println("N=" + TestOpownmAlgorithm.argorithmCount + ": " + numArray.get(i) + ": " + loopNumWord);
			if(innerNest > 0){
				onpowernAlgorithm(numArray, algorithmDataCount, innerNest);
			}else{
				TestOpownmAlgorithm.argorithmCount++;
			}
        }
		return 0;
	}
}

指数時間（O(2^N)）:

class TestOpow2nAlgorithm {
	//O(2^N)のアルゴリズム例：部分集合を全て取得
	static int argorithmCount = 1;
    public static List<List<Integer>> opow2nAlgorithm(List<Integer> numArray) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(numArray, 0, new ArrayList<>(), result);
    	for(int i = 0; i < result.size(); i++){
			System.out.println("N=" + TestOpow2nAlgorithm.argorithmCount + " " + result.get(i));
    		TestOpow2nAlgorithm.argorithmCount++;
		}
        return result;
    }
    
    private static void backtrack(List<Integer> numArray, int index, List<Integer> current, List<List<Integer>> result) {
        if (index == numArray.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        // indexの要素を含める
        current.add(numArray.get(index));
        backtrack(numArray, index + 1, current, result);
        
        // indexの要素を含めない
        current.remove(current.size() - 1);
        backtrack(numArray, index + 1, current, result);
    }
}

階乗時間（O(N!)）

class TestOfactrialnAlgorithm{
 	//O(N!)のアルゴリズム例：要素の全順列を取得
    static int argorithmCount = 1;
    public static void ofactrialnAlgorithm(List<Integer> numArray, int start) {
    	 List<List<Integer>> result = new ArrayList<>();
        if (start == numArray.size() - 1) {
            result.add(new ArrayList<>(numArray));
        	System.out.println("N=" + TestOfactrialnAlgorithm.argorithmCount + " " + numArray);
        	TestOfactrialnAlgorithm.argorithmCount++;
            return;
        }
        for (int i = start; i < numArray.size(); i++) {
            Collections.swap(numArray, start, i);
            ofactrialnAlgorithm(numArray, start + 1);
            Collections.swap(numArray, start, i);
        }
    }
}

アルゴリズム実施結果

単位：ミリ秒（※）

	10個のデータ (N=10)	100個のデータ (N=100)	1,000個のデータ (N=1,000)	10,000個のデータ (N=10,000)
$O(1)$	14	14	15	13
$O(log(N))$	16	17	20	20
$O(N)$	17	28	68	398
$O(Nlog(N))$	19	91	902	29070
$O(N^2)$	26	727	69120	計測不能
$O(2^N)$	123	計測不能	計測不能	計測不能
$O(O(N!))$	215218	計測不能	計測不能	計測不能

※状況によって誤差が生じます

参考URL：
https://zenn.dev/shoan/articles/d13f3dde7c8400
https://mathlandscape.com/landau-o/

著者: K.K (株式会社ウィズツーワン)