# Big O - 基礎 & O(n)

## 前言
之前一直以為前端只要把版切好，有點美感就好了。

後來發現學了 TypeScript 可以讓我在三個月回來看自己的 code 時還可以看懂；發現學了自動化 CI/CD 可以讓我不用為了部署而花費大把時間。

而 Big O 呢？曾經以為前端相對於後端，應該比較少會遇到資料結構或演算法的考驗，但當我想要邁向資深工程師這條路，「效能調整」就是一個重要的議題。所以希望可以把之前沒有打很好的底重新拿出來複習一次。

Let's Go! To the Big O World :rocket:

:::info
以下學習筆記皆是從 Udemy - Master the Coding Interview: Data Structures + Algorithms 這堂課整理出來的
:::

## O?

維基百科：

大O符號（英語：Big O notation），又稱為漸近符號，是用於描述函式漸近行為的數學符號。更確切地說，它是用另一個（通常更簡單的）函式來描述一個函式數量級的**漸近上界**。在數學中，它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項；在電腦科學中，**它在分析演算法複雜性的方面非常有用**。

大O符號是由德國數論學家保羅·巴赫曼在其1892年的著作《解析數論》（Analytische Zahlentheorie）首先引入的。而這個記號則是在另一位德國數論學家愛德蒙·蘭道的著作中才推廣的，因此它有時又稱為蘭道符號（Landau symbols）。代表「order of ...」（……階）的大O，最初是一個大寫希臘字母「Ο」（omicron），現今用的是大寫拉丁字母「O」。

## 什麼是好 code？

先討論這兩點：

- 可讀性（Readable)
- 可擴展性（Scalable)

第二點就是 Big O 可以去評斷的了。

用 `for` 迴圈舉一個最基本的例子：

const dog = ['dog']

function findDog(array){
    for(let i = 0; i < array.length; i++)
        {
            if(array[i]==='dog'){
                console.log('FoundDog!')
            }
        }
}

findDog(dog)

我們要怎麼去評斷這個 `for` 函數的效率呢？

## 計算時間

JavaScript 方法除了 Date.now() 可以得知當下時間，我們也可以透過 `performance.now()` 來計算以毫秒為單位的時間。

讓我們加入函數中：

const dog = ['dog']

function findDog(array) {
   let t0 = performance.now();
   for (let i = 0; i < array.length; i++) {
      if (array[i] === 'dog') {
         console.log('FoundDog!')
      }
   }
   let t1 = performance.now();
   console.log('Call to find Dog took ' + (t1 - t0) + ' milliseconds');
}

findDog(dog)

此時去執行，就可以看到毫秒被印出來。

replit 執行結果。每執行一次都會不太一樣。

接下來，如果把執行的陣列增長，執行時間會變得如何？

可以發現陣列如果放入任意的十個物件，執行的時間並不會差到太多，這是因為電腦處理的速度很快。

但如果把陣列長度變成 1000, 10000 呢？讓我們用 `new Array(1000).fill('dog')` 來創造一個很大的陣列，看看執行結果如何。

const dog = ['dog']

const largeArray = new Array(1000).fill('dog');

function findDog(array) {
   let t0 = performance.now();
   for (let i = 0; i < array.length; i++) {
      if (array[i] === 'dog') {
         console.log('FoundDog!')
      }
   }
   let t1 = performance.now();
   console.log('Call to find Dog took ' + (t1 - t0) + ' milliseconds');
}

findDog(largeArray)


此時可以看到執行時間變成 20 毫秒左右。時間明顯增加了。

### 小結
透過這個結果，我們可以說，這個函數隨著 input 增加，執行次數就會越多，所需時間就會越長。

而結果不是每一次執行都是穩定的，會隨著機器的狀態而改變，但我們可以看出這個趨勢。

這也就是 Big O 想要分析的，當 input 變多，執行次數能不能仍然很少很少？如果可以，代表這個函數很有效率。反之亦然。

## O(n)

### 線性增長

前面提到 `for` loop 的例子，可知當 `dog` 陣列裡多了一個元素，`findDog` 函數就要多執行一次。執行的時間取決於陣列的長度（n)，用圖表表示，他是一種線性增長（linear growth)。這個函數的時間複雜度為 O(n)。英文講法是 O-n 、O of n 或 Big O of n。


### Big O 講的是最糟的情況
假設陣列的長度為 1000，最糟的情況下若 'dog' 排在最後面，要執行到第 1000 次我們才能找到目標。最好的狀況則是第 1 次就找到了。由於實際電腦執行程式也會每次都獲得不一樣的結果，Big O 就會以「最糟情形」為準來判斷演算法的優劣。

可以看到在分佈圖中，O(n)算是 fair 等級的。