[TIL 14][Data Structure]Big O Notation

10285 ワード
TIL data structure テキストリンク

概要

  • アルゴリズム性能の数学的表現
  • アルゴリズムの時間と空間の複雑さ
  • アルゴリズムのデータまたはユーザ成長率予測目標は
    • である.

    を選択します。


    O(1)


  • データ増加時の性能は変わらない

    • code

    let n = [];
function f() {
  return (n[0] === 0) ? true : false;
}

    O(n)



    アルゴリズム
  • の処理時間は入力データのサイズに比例する

    code

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

    O(n²)


  • n個のデータ、n回の処理回数が
    • 増加
  • データが大きいほど処理時間が長くなり負担が重くなる

    Code

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

    O(nm)


  • n²同様にnを考慮することができる²

    • code

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

    O(n³)


  • n²乙nは再循環する.3 D...?

    • code

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

    O(2^n)


  • Fibonacci数列と同じ

    • code

    function f(n) {
    if(n <== 0) return 0;
    else if(n === 1) return 1;
    return f(n - 1) + f(n - 2);
};

    O(log n)


  • の代表的なアルゴリズムには、バイナリ検索
    • がある.
    関数
  • が呼び出されるたびに、中間値に基づいて半分が検索領域から除外されるため、順序検索よりもはるかに高速である
    • .
    これはバイナリ検索を整理するときに、追加コードが必要です.
    iOS開発Google Protocol Bufferの解析パッケージ(二)
    2021.07.05 TIL:できますか.