計算量とオーダー記法ランダウの記法、線形、累乗、指数関数、forループ、3重、組み合わせ

学習環境

問題解決力を鍛える!アルゴリズムとデータ構造 (大槻兼資(著)、秋葉拓哉(監修)、講談社)の第2章(計算量とオーダー記法)、章末問題2.1、2.2の解答を求めてみる。

2.1

\begin{array}{l} T_{1} (N) = O (N) \\ T_{2} (N) = O (N^{2}) \\ T_{3} (N) = O (N^{2}) \\ T_{4} (N) = O (N^{\frac{3}{2}}) \\ T_{5} (N) = O (2^{N}) \end{array}

2.2

0 \leq i < j < k < N

よって、

(\begin{matrix} N \\ 3 \end{matrix}) = \frac{N!}{(N - 3)! 3!} = \frac{N (N - 1) (N - 2)}{3!}

ゆえに求める計算量をラウダウの記法を用いて表したものは、

O (N^{3})

実際に確認してみる。

コード

package main

import "fmt"

func p(n int) int {
	return n * (n - 1) * (n - 2) / 6
}
func main() {
	for n := 0; n < 10; n++ {
		count := 0
		for i := 0; i < n; i++ {
			for j := i + 1; j < n; j++ {
				for k := j + 1; k < n; k++ {
					count++
				}
			}
		}
		fmt.Println(count, p(n), count == p(n))
	}
}

入出力結果

% go run main.go
0 0 true
0 0 true
0 0 true
1 1 true
4 4 true
10 10 true
20 20 true
35 35 true
56 56 true
84 84 true
%