# Day 31 : 初識複雜度

## 前言
如果把演算法看成是解決問題的過程、步驟，複雜度(Complexity)就是用來分析這個演算法是好還是壞的一個方法，在這個主題則是先聚焦在時間複雜度(Time Conplexity)和Big O。

要介紹複雜度前要先引入一個概念，叫做「Operation」，一般來說執行程式碼時，任何一次使用加、減、乘、除、大於等於之比較都可以稱為「Operation」。而複雜度$f(n)$就是當我們有個輸入n的時候，在執行某個演算法你需要執行的operation數量。

在下面的程式碼的例子我們用counter來累計每次有需要計算的次數，在第一個部分，因為迴圈會循環$5*n$，所以counter增加$5*n$，在第二個迴圈則是會循環n^2次，所以counter會再增加$n^2$次，最後只做單純的加上七次。如果以函式顯示複雜度和input size的關係則如下

f(n) = 5*n + n*n + 7

將橫軸看成input size - $n$，縱軸為複雜度 - $f(n)$，可以得到一個二次函式的圖形，且開口朝上，經過後得到斜率為$2 \times n+5$，x軸越大y軸增加的速度就會越快，也符合在程式碼中實際得到的結果。

(圖一， 自行繪製)

package main

import (
	"fmt"
)

func main() {
    fmt.Println(countComplexity(2))   // 21
    fmt.Println(countComplexity(3))   // 31
    fmt.Println(countComplexity(4))   // 43
    fmt.Println(countComplexity(5))   // 57
    fmt.Println(countComplexity(100)) // 10507
}

func countComplexity(n int) int {
    counter := 0
    
    // 第一部分
    for i := 0; i < 5*n; i++ {
        counter++
    }
    
    // 第二部分
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            counter++
        }
    }
    
    // 第三部分
    counter += 7
 
    return counter
}

## Big O Notation

先看一下[維基百科](https://en.wikipedia.org/wiki/Big_O_notation)的定義 :
> *Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.*

其實有點像微積分裡面極限的想法，這邊的argument參數可以看成input size， Big O Notation就是在描述當n越來越大的時候，$f(n)$會趨近的地方。

計算Big O 的值需要考慮的是The worst case，也就是最糟糕的情況下演算法要執行很多次，有時候可以發現當input size很大，有些項目的影像會很小，這邊舉例下列三點:

* 常數可以省略
假設有一個$f(n)=7n$，前面的常數7就可以忽略，Big O的值可以寫成$O(n)$
* 影響較小的趨勢可以省略
假設有一個$f(n)=n^2+7n+30$，前面的常數7就可以忽略，Big O的值可以寫成$O(n^2)$
* 對數的base可以忽略
假設有一個$f(n)=log_{2}{(n)}$，Big O的值可以寫成$O(log(n))$

## Deeper Understanding - Big O Notation
上面為比較簡單的說法，在這裡透過Asymptoitic notation與數學上比較嚴謹的定義來學Big O。
Asymptoitic會有一點rough的概念，希望探討當n夠大的時候行為，可以先看看圖二，橫軸一樣是input size，縱軸是複雜度，如果有紅色線$f(n)=n^3$，藍色線為$g(n)=8n$，當輸入值比較小的時候在第一區塊的時候，可能會覺得$f(n)$比較好，但Asymptoitic notation這邊要探討的其實是當input size夠大的時候，大概會發生什麼事，大概可以怎麼描述這個函數，也就是圖二的第二區塊。

(圖二， 自行繪製)

當我們要稱$f(n)$是$g(n)$的Big O，可以寫成$f(n)=O(g(n))$，定義如下

:::info
$The\ function\ of f(n)=O(g(n)) \ \ \ iff \ \ \exists \ c,n_0$
$s.t. \ \ 0\le f(n)\le c\times g(n)\ \ , \ \ \forall \ \ n\ge n_0$
:::

換句話來說，有存在一個$n_0$時，當我們有足夠大的$n$的時候，$c\times g(n)$會永遠大於$f(n)$，可以將$c\times g(n)$視為$f(n)$的upper bound，如下圖。

(圖三，資料來源:Educative.io)

如果實際假設一個$f(n)=2n^2+3n+6$、$c=5$、$g(n)=n^2$，藍色線條為$f(n)$，紅色線條為$cg(n)$，可以當$n_0=2$的時候，$f(n) \le cg(n)$，所以可以將$f(n)$看成$O(g(n))$，也就是$f(n)=O(n^2)$。

(圖四， 自行繪製)

以極限來看則如下:

$\displaystyle\lim_{n\to\infty} f(n) \le cg(n)$

## Big Omega
Big O定義了upper bound，Big Omega則相反定義了lower bound，而為什麼我們會需要omega呢，想想不論我們如何優化這個演算法，總是會達到一個臨界值，讓這個函式不會再變得更好，定義如下

:::info
$The\ function\ of f(n)=\Omega (g(n)) \ \ \ iff \ \ \exists \ c,n_0$
$s.t. \ \ 0\le c\times g(n)\le f(n)\ \ , \ \ \forall \ \ n\ge n_0$
:::

(圖五，資料來源:Educative.io)

## Big Theta
找到upper bound是Big O，找到lower bound是Big Omega，同時找到upper bound和lower bound就是Big Theta

:::info
$The\ function\ of f(n)=\Theta (g(n)) \ \ \ iff \ \ \exists \ three\ \ positive\ \ constants\ \ c_1,c_2,n_0$
$s.t. \ \ 0\le c_1\times g(n)\le f(n)\le c_2\times g(n)\ \ , \ \ \forall \ \ n\ge n_0$
:::

(圖六，資料來源:Educative.io)

## Referencs
1. [資料結構與演算法 (JavaScript) - Wilson Ren](https://www.udemy.com/course/algorithm-data-structure/)
2. [Complexity：Asymptotic Notation(漸進符號)](http://alrightchiu.github.io/SecondRound/complexityasymptotic-notationjian-jin-fu-hao.html)
3. [List of LaTeX mathematical symbols](https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols#Set_and.2For_logic_notation)

###### tags: `Algorithm`、`Big O`