データ構造とアルゴリズム【JavaScript版】—複雑度計算

7792 ワード

データ構造 javascript アルゴリズム時間の複雑さ空間複雑度

時間複雑度計算
時間の複雑さは何ですか?

の関数は、O(1)、O(n)、O(logN)…

のような大きなO表現を使用しています.

時間の複雑さは、アルゴリズムの実行時間を定性的に記述するための

である.
インスタンスコード

O(1)

let i = 0;
i += 1;

O(n)

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

O(1)+O(n)=O(n)

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

O(n)＊O(n)=O(n^2)

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

O(logN)

let i = 1;
while(i < n) {
	console.log(i);
	i *=2;
}

空間複雑度計算
空間の複雑さは何ですか?

の関数は、O(1)、O(n)、O(n)…

のような大きなOで表されています.

空間複雑さは、アルゴリズムが実行中に一時的に記憶空間サイズを占有するメトリック

である.
インスタンスコード

O(1)

//         ，              
let i = 0;
i += 1;

O(n)

//        ，       n  ，      n     
const list = [];
for (let i = 0; i<n; i+=1) {
	list.push(i);
}

O(n^2)

//           
const matrix = [];
for (let i = 0; i<n; i+=1) {
	matrix.push([]);
	for (let j = 0; j<n ; j+=1) {
		matrix[i].push(j);
	}
}