Big O notation

就活のためアルゴリズムやデータ構造の勉強を改めてやることにしました。今回 Big O 記法の勉強したのでそのまとめ。

まず、良いコードとは？

Readable
Scalable (Speed of runtime, Memory) -> Big O で測れる

コードを実行する際、それを実行するコンピューターの性能に依存するのではなく、プログラムそのものの性能を図るための指標として用いられる記法のこと。

Speed of runtime: インプット量が増える度に実行時間が比例してどのくらい増えるか(オペレーションの数が増えるか)

以下のチャートで、インプット数とオペレーションの数の関係がまとめられている。
プログラムを書く時、なるだけ Excellent になる Time Complexity を目指すべし。

基本

O(n) - Linear Time

インプットが増えるに伴い、オペレーションの数も比例して増える。

const arr = ['apple', 'banana', 'peach'];

function findApple(array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'apple') {
      console.log('Found Apple!');
      // break ->見つけた時点で抜け出せるけど、最悪は最後までループするのでそのケースを想定
    }
  }
}

findApple(arr); // O(n)   --> Linear Time

O(1) - Constant Time

インプットが増えてもオペレーションの数は変わらない。必ず2回のオペレーションステップでい続けるので、グラフの場合線は並行である続ける。

const boxes = [0, 1, 2, 3, 4, 5];
function logFirstTwoBoxes(boxes) {
  console.log(boxes[0]); //O(1)
  console.log(boxes[1]); //O(1)
}

logFirstTwoBoxes(boxes); // O(2) everytime  -> O(1)

O(n^2) - Quadratic Time

ネストループ

// O(n^2)
const nums = ['a', 'b', 'c', 'd', 'e'];
function logAllPairsOfArray(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      console.log(array[i], array[j]);
    }
  }
}

Time Complexity を計算する上でのルールがある。

BIG O ルール

Worst Case

（例：ループだと、一致するものを途中で見つける可能性もあるが、最悪のケース、毎回最後までループしなければいけないケースを想定する）
Remove Constant

(例：2n+ 100) -> O(n)となる。より多くのインプット量を想定したとき、誤差の範囲内になる)
Different terms of input

(例:input が複数の場合。O(a + b) or O(a*b)と、Big O もそれぞれ用意。

-> same indentation-> add

-> anything different -> multiply というのが簡単な計算方法。
Drop Non Dominants
(2 と同じ考え方)

まとめ　

O(1) Constant

ループなし

O(log N) Logarithmic

通常は、Binary SearchなどのSearching AlgorithmsがO(log N) (ソートされてる前提)

O(n) Linear

n回for loopやwhile loopsを行う

O(n log(n)) Log Linear

大抵はSorting operation

O(n^2) - Quadratic

コレクション内のすべての要素を比較する、 two nested loops

O(2^n) - Exponential

Nサイズの問題を解決するrecursive algorithm

O(n!) - Factorial

すべての要素にループを追加

　実行時間だけではなく、メモリの使用量もBig O で測ることができる。

Space Complexity

2 ways of storing memory　

Heap: store variables that are assigned　

stack: function calls

参考

こちらのUdemyで勉強しています。　
Master the Coding Interview: Data Structures and Algorithm

グラフの参考はこちらのサイトです。　
Big-O Cheat Sheet