Big-O

4856 ワード

アルゴリズム#アルゴリズム# テキストリンク

アルゴリズム性能の数学的表現

アルゴリズムの性能予測の目的は、実際の実行時間ではなく、ユーザ成長率に基づいてアルゴリズムの性能を予測することである.

Big-Oは時間的複雑度、空間的複雑度がある.

実行アルゴリズムの演算回数(実行時間ではなく)を数値としてマーク

演算回数をデータ数nと表す関数を時間複雑度関数と呼ぶ

不要な時間的複雑度演算を排除し、時間的複雑度をマークしてデータの増加による処理を簡素化
最悪の場合、計算時間効率であるため、処理するデータの数が十分多いと仮定します.

定数アイテムを無視
データ(n)サイズの影響で定数項を除く.O(2n), O(3n) => n

影響なしを無視
データ(n)サイズの影響で,最も影響力のある項目を除いては無視された.O(n^2 + n) => O(n^2)

入力データのサイズにかかわらず、アルゴリズムは同じ処理時間を必要とします.

function add(n) {
	console.log(n + n);
}
// n의 크기에 상관없이 연산은 한번만 일어나므로 O(1)

例)バイナリ検索

処理の半分当たりの処理時間が

減少する.

入力データサイズに比例するアルゴリズムの処理
nが10なら10番!

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

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

アルゴリズム

の初期成長は遅いが,データの増加に伴って処理時間が急激に増加した.

例)冗長

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

メモリ使用量

この問題について(Big-O), 我々は、より多くの情報をここで見つけました https://velog.io/@jing07161/Big-O-표기법

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol