[CS] Time Complexity Day-46

時間の複雑さ

演算を実行する場合、入力値の変化は演算回数に比べてどのくらい時間がかかりますか?

これは,入力値が大きくなるにつれて増加する時間パーセントを最小化するアルゴリズムを構築することを意味する.

時間の複雑さは、通常、大きな記号から小さな記号で表されます.

Big-O記号

Big-O

メガΩ

Big-θ

O(1)

入力値の変化に応じて演算を実行する際の演算回数に対する所要時間を表す方法.これを定数複雑度と呼び,入力値が増加しても時間は増加しない.入力値のサイズにかかわらず、出力値はすぐに取得できます.

function O_1_algorithm(arr, index) {
	return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

O(n)

これを線形複雑度と呼び,すなわち入力値が増加するにつれて時間も同様の割合で増加する.
ex)O(2 n)の場合、結果値を返す時間は2倍になります.別の例が5 nの場合、結果を返す時間が5倍になる可能性があります.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O(log n)

O(1)時間的複雑度が最も高かった.
「バイナリ検索ツリー」(BST)で必要な値をナビゲートすると、ノードを移動するたびに状況の数が減少します.

O(n^2)

これを二次複雑性と呼び,入力値が増加するにつれて時間がnの平方数の割合で増加することを示す.
nが大きいほど指数の影響力は小さくなる.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

O(2^n)

これを指数複雑度と呼び,Big‐O符号の中で最も遅い時間複雑度である.
実装アルゴリズムの時間的複雑度がO(2^n)である場合、別の方法が必要である.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}