個人メモです。
・Big O Notaion: ビッグオー表記法のセクション。
ビッグは難しいとかではなく、重要という意味。
- 処理にかかる計算量を数学的に表したもの。
- 単語や色わけではなく数字なので、直感的にわかりやすい（意味を理解すれば）
- 巨大なデータの効率的な処理で重要な概念
- 最適なアルゴリズムを選択するために使用する
いいアルゴリズムとは？
いいアルゴリズムとなるための重要な指標は２つ。
・早さ
・メモリ使用量
時間処理量の注意点
時間で処理速度を比較するには問題点がある。
同じマシンで処理を行ったとしても、実施するタイミングで処理時間が異なる。
超巨大なデータを処理することで違いを明確にすることはできるが、処理速度の比較のために数時間もかかる処理を回すのは本末転倒。
このため、処理時間での比較は適切でない。
それが、 Big O notice(O表記法)。
### メモリ使用量
PCの性能や、実行タイミングに寄らずに処理量を比較するため、処理プロセスの数で比較する。
**▼処理量(operation)の数を数えるとは？** 四則演算処理の回数を処理量として数える。function addUpTo(n){
return n * (n+1)/2;
}
上記例だと、「*」、「+」、「/」の３つが使われているので、処理量は３となる（3 operations）
数値は関係ない。1,000,000,000だろうが3だろうが処理量には関係ない。
この時のO表記法はO(1)となる。
O(1)は投入するデータ量によって、処理量は変化しないという意味。
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」となる。
#### 「n」のもつ意味 O表記法で「n」がでてきたが、これは処理量が投入したデータ量に比例することを表している。
投入するデータ量が増えれば増えるほど、比例して処理速度が増加していく。
例１の場合、処理量は３なので、100を投入しようが、1000,000,000,000を投入しようが処理量は同じ。
### nの２乗になる処理
O(n)の処理が並列して続く場合、処理量はnになる。
例
0(n)の処理の後に、0(n)が続くなら、処理量は「2n」。係数は無視するので、結局「n」になる。
2nだろうが、50nだろうが投入データ量に対して処理量が比例することは変わらない。
O(n2)となるのは、O(n)の処理の中にO(n)が入っている場合。
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)が最も処理速度が早いアルゴリズム。
log nは2低が省略されている。2をn乗すると指定した値になる数値が解。
## Space Complexity(空間処理量) 先ほどまではtime complexity（時間処理量）を見てきたが、空間処理量という概念も存在する。
これは、どれだけの変数を定義したかで処理量を量っている。
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)
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)」となる。
## 英単語 ・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: ログ。対数