2021_04_19

TIL - Time Complexity

1.時間の複雑さ（時間の複雑さ）

アルゴリズムを記述する際に,時間の複雑さに関する議論を聞いたことがあるかもしれない.
アルゴリズムの時間的複雑さは、「入力値が変化するにつれて、問題を解決するのに要する時間の割合がどのように変化するか」を表します.従って、効率的なアルゴリズムは、入力値の増加に伴って増加する時間パーセントを最小化するアルゴリズムと言える.
標記時間の複雑さの方法の中で最も代表的な方法はBig−O標記法である.最悪の場合、入力値が増えるにつれて、時間がどれだけ増えるかです.そこで今日はBig-Oマーキング法の種類を学びます.
1) O(1)
定数複雑度と呼ばれ,入力値が増加しても時間が増加しないことを示す.たとえば、次のアルゴリズムがあるとします.

function 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

上記のアルゴリズムでは,配列とインデックスをパラメータに渡し,配列インデックスに対応する値を返す関数である.上記のアルゴリズムを実行する時間を1秒と仮定すると、arrの長さが50100に増加しても、対応するインデックスを見つけるだけで、所要時間は同様に1秒かかる.
従って、上記アルゴリズムでは、入力値の大きさにかかわらず、直ちに出力値を得ることができる.
2) O(n)
これを線形複雑度と呼び,入力値が増加するにつれて時間も同様の割合で増加することを意味する.例えば、次のようなアルゴリズムがあるとする.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
          console.log(i);
	}
}
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	  console.log(i);
	}
}

O nアルゴリズムでは,iが1増加するごとに,iがnの関数に出力される.
入力値(n)を1つ増加するごとに、コードの実行時間が増加します.すなわち、入力値が増加するにつれて、同じ割合でかかる時間が増加している.
other O nアルゴリズムにおいても同様である.2 n増加毎にO(2 n)であるが,Big−Oマーキング法ではO(n)である.nが増加するにつれてその割合は非常に大きくなるため,係数は次第に意味を失う.
3) O(log n)
対数複雑性と呼ばれ,バイナリプローブツリーに関係する.
アルゴリズムは実行するたびに半分減少して実行されます.たとえば、次のコードがあるとします.

let i = n;
while(parseInt(i) > 0) {
 i = i / 2;
}

上記のアルゴリズムは,nを入力することでwhile文で1/2の減少を継続する.
したがって,時間的複雑さはO(logn)と呼ぶことができる.
4) O(n^2)
二次複雑性とは,入力値の増加に要する時間が二乗比で増加することを意味する.例えば、次のようなアルゴリズムがあるとする.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
	            console.log(j);
		}
	}
}

nが1と入力されると1秒かかる.nを5と入力すると、5^2の時間がかかります.したがって,時間的複雑度はO(n^2)である.
5) O(2n)
これは指数複雑性と呼ばれ,アルゴリズムが実行されるたびに2倍の時間がかかることを意味する.
例えば、次のようなアルゴリズムがあるとする.

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

n回のフィボナッチ数を求めるためには、n-1,n-2回のフィボナッチ数を求める必要があるので、1+2+4+8+・・+2^(n-1)次演算が必要です.従って,時間複雑度はO(2 n)であった.
これまで学んだマーキング法の時間的複雑度の大きさを比較する.

この授業では大文字法と時間の複雑さを学びました.
明日はアルゴリズムをもっと勉強する時間があります.
今日はここまで