Zenn
📝

Big O Notation(Big O 記法) について

2021/12/31に公開
アルゴリズム
tech

Big O 記法とは

  • アルゴリズムの性能を記述するために使う表記
  • 「O」はオーダー(Order)という単語に由来し、ランダウの記号などとも呼ばれ、実行されるアルゴリズムが、どれほどの時間、記憶領域を使用するかを評価するも基準として用いられる

代表的なオーダー

表記 意味 例 早い順
O(1) 定数 配列を添字アクセスする場合（ex. a[0] = 1;） 1
O(log(n)) 対数 二分探索 2
O(n) 一時 線形探索 3
O(n log n) nlog n クイックソート 4
O(n**2) 二次 バブルソート 5

O(1)

命令数がデータ数に比例することを意味する。
データ量と関係なく、処理時間が一定のオーダーでもっとも早い

// O(1)
func oOne(numbers []int) {
	fmt.Println(numbers[0])
}

O(log n)

処理するたびにターゲットが絞られて早くなるオーダー
O(N) に比べてかなり早い

// O(n * log(n))
func oNLongN(n int) {
	for i := 0; i < n; i++ {
		fmt.Print(i)
	}

	fmt.Println()
	if n <= 1 {
		return
	}

	oNLongN(n / 2)
}

O(n)

データ量に応じて処理時間が比例するオーダー
for 文で配列の中身を全部表示しようとするときがこれにあたる

// O(n)
func oN(numbers []int) {
	for _, i := range numbers {
		fmt.Println(i)
	}
}

O(n log n)

学術的にはこちらが処理速度の基準とされているオーダー
O(N) より少しだけ遅い

// O(n * log(n))
func oNLongN(n int) {
	for i := 0; i < n; i++ {
		fmt.Print(i)
	}

	fmt.Println()
	if n <= 1 {
		return
	}

	oNLongN(n / 2)
}

O(n**2)

二重ループ
O(N) に比べてかなり遅い

// O(n**2)
func oN2(numbers []int) {
	for _, i := range numbers {
		for _, j := range numbers {
			fmt.Println(i, j)
		}
		fmt.Println()
	}
}

参考資料

Discussion