(2)Big O Notation - JS Algorithms and Data Structures Masterclass

個人メモです。

・Big O Notaion: ビッグオー表記法のセクション。
ビッグは難しいとかではなく、**重要**という意味。


 - 処理にかかる計算量を数学的に表したもの。
 - 単語や色わけではなく数字なので、直感的にわかりやすい（意味を理解すれば）
 - 巨大なデータの効率的な処理で重要な概念
 - 最適なアルゴリズムを選択するために使用する
 

##いいアルゴリズムとは？
いいアルゴリズムとなるための重要な指標は２つ。

・早さ
・メモリ使用量


###時間処理量の注意点
時間で処理速度を比較するには問題点がある。

**同じマシンで処理を行ったとしても、実施するタイミングで処理時間が異なる**。

超巨大なデータを処理することで違いを明確にすることはできるが、処理速度の比較のために数時間もかかる処理を回すのは本末転倒。

このため、**処理時間での比較は適切でない**。

それが、 Big O notice(O表記法)。


<br>
###メモリ使用量

PCの性能や、実行タイミングに寄らずに処理量を比較するため、**処理プロセスの数**で比較する。

<r>
**▼処理量(operation)の数を数えるとは？**
四則演算処理の回数を処理量として数える。

```js:例１
function addUpTo(n){
    return n * (n+1)/2;
}
```

上記例だと、「*」、「+」、「/」の３つが使われているので、処理量は３となる（3 operations）

数値は関係ない。1,000,000,000だろうが3だろうが処理量には関係ない。

この時のO表記法はO(1)となる。
O(1)は投入するデータ量によって、処理量は変化しないという意味。

<br>

```js:事例２
function addUpTo(n) {
    let total = 0;
    for (let i=1; i<=n; i++){
        total += i;
    }
```

この場合、オペレーション数は、5n+2になる。

>「let total=0;」:1回（代入処理）
「let i=1」: 1回（代入処理）
「i <=n」：n回（比較処理）
「i+1」：n回（加算処理）
「i=i+1」:n回（代入処理）
「total + i」：n回（加算処理）
「total = total+i」：n回（代入処理）


>※「++」や「+=」は加算と代入の２つの処理を含む。


O表記法では、５や２など細かい数字には着目せず、抽象的な大きさにのみ着目する。

上記計算の場合の処理量は「n」となる。

<br>
####「n」のもつ意味
O表記法で「n」がでてきたが、これは処理量が投入したデータ量に比例することを表している。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563526/063f1f89-441f-36c7-de49-2c713dd2789a.png)
投入するデータ量が増えれば増えるほど、比例して処理速度が増加していく。


例１の場合、処理量は３なので、100を投入しようが、1000,000,000,000を投入しようが処理量は同じ。



<br>
###nの２乗になる処理

O(n)の処理が並列して続く場合、処理量はnになる。

>例
0(n)の処理の後に、0(n)が続くなら、処理量は「2n」。係数は無視するので、結局「n」になる。

2nだろうが、50nだろうが投入データ量に対して処理量が比例することは変わらない。


O(n2)となるのは、O(n)の処理の中にO(n)が入っている場合。

```js:O(n2)事例
function printAllPairs(n){
    for (var i=0; i<=n; i++){
        for (var j=0; j<=n; j++){
            console.log(i,j)
        }
    }
}
```

上記の場合、for文でO(n)の処理の中でO(n)の処理が繰り返されている。

このため処理量は「n*n = n^2」となる。


実際の処理も、n=1のときは下記４つだが、
(0,0)(0,1)(1,0)(1,1)


n=2の時は、9個になる。
(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(2,2)


処理量はデータ量に比例せず、大幅に増加していることがわかる。




###O表記法の投入データ量と処理量グラフ
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2)

O(1)が最も処理速度が早いアルゴリズム。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563526/fdcee6aa-e5f1-7853-bfe4-4888f97d7e51.png)

log nは2低が省略されている。2をn乗すると指定した値になる数値が解。



<br>
##Space Complexity(空間処理量)
先ほどまではtime complexity（時間処理量）を見てきたが、空間処理量という概念も存在する。

これは、どれだけの変数を定義したかで処理量を量っている。

```js:例1
function sum(arr){
    let total=0;
    for (let i=0; i<arr.length; i++){
        total += arr[i]
    }
    return total
}
```

上記例の場合、定義される数値は「total」と「i」の２つ。このためO表記方はO(1)となる。

変数量が１0でも1000でも、O表記はO(1)


<br>

```js:例２
function double(arr){
    let newArr = [];
    for (let i=0; i<arr.length; i++){
        newArr.push(2*arr[i]);
    }
    return newArr
}
```

上記例の場合、新たに定義される数値は「newArr=[ ]」と「i=0」、また、newArr.pushで指定した配列番号に新しい数値を入れていくので、arrの配列番号の数だけ新しい数値入力を繰り返す。

このためO表記は「O(n+2)」->「O(n)」となる。







<br>
##英単語
・indicative: 指標

・time complexity: 時間計算量。処理にどのくらいの時間がかかるか（どれだけ複雑か）

・space complexity: 空間計算量。処理にどれくらいのメモリが必要か（記憶処理が複雑か）

・bullet point: 箇条書きの項目。first bullet pointは最初の項目。

・two valid solution: ２つの有効な解決手法。

・off the top of my head: 思いつきで

・ish： 〜ぐらいの。イッシ。three ishで３つぐらい。

・be content with: ~に満足する

・cut and dry: 型にハマった、決まり切った。

・debug: ディバグ。デバッグは日本語発音。

・lagging: 遅れる。処理が遅い。

・rambling: とりとめのない

・less intuitive: 直感的でない（わかりにくい）

・brevity: 手短か（brief）

・plot: プラット。※発音はプロットではない。

・jibberish: 出まかせのおしゃべり。gibberish

・square: 2乗

・vary: ベリー。変わる

・quadratic: ２乗

・elongate: 細長くする

・`math.max(val1, val2,,,)`: 最大値を返す

・`math.ceil(式)`:繰り上げ

・auxiliary: アギジャラリー。補助的な

・repercussion: レプレカッション。影響

・null: ナァル。ヌルじゃない、、

・logarithms:　ログ。対数