3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@With21(ウィズツーワン)

アルゴリズムの計算量について

3
Posted at

プログラムを繰り返し処理する際、手順数が爆発的に増えると、計算が追い付かなくなり、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 (株式会社ウィズツーワン)

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?