時間複雜度 — 漸進函數
相信有在學習程式的各位一定常常聽到「時間複雜度」一詞，礙於之前對於Big-O, Omega, theta的概念一直處於一知半解的狀態，導致目前大概是學幾次就忘幾次，決定透過這次把它好好記下來。
由於這學期有選修演算法相關的課程，想透過這次機會邊上課學習邊做筆記。還希望各位讀者看過這篇過後，可以理解其中的意含。
先前對於Ｂｉｇ－Ｏ的記憶：
Big-O：時間複雜度最糟的狀況。
Omega：時間複雜度最好的狀況。
Theta：時間複雜度平均的狀況？？
如果各位對於時間複雜度的概念，就像我一樣的話，很希望這篇可以帶給各位一些新的觀念與想法。那就讓我們開始吧~~
本篇章節：
1. 漸進符號的功能
2. 介紹各個漸進符號 （Big-O, Omega, Theta, Little-O, Little-Omega）
1. 漸進符號的功能（Asymptotic notation）
為甚麼會需要漸進符號呢？
—> 用來粗略估計時間複雜度的工具/手段。
簡單的定義：
當 n -> 無限大, T(n)函數所估計的時間複雜度。------------------------------------------------
＊這邊的T(n)不是什麼可怕的東西，只是一個函數的關係而已。＊函數不可怕，其實只要想成是「存在某種關係」就對了。
------------------------------------------------例如：
今天某某店全面打九折，所以他們的收銀機可能會出現下方的函式。
當看到某商品售價500元，我們很直觀地想說，打9折，不就是乘上0.9就好了嗎
心中算盤開始運作 500 * 0.9 = 450元 那我們把它轉換成數學的樣子來呈現：
f(x) = 0.9 * x 售價(y) = f(x) = 0.9 * x，其中 x 代表商品的原價。
而f(x)所代表的是：「商品原價 x 」跟「售價 y」有9折的「關係」。
如果還不太清楚粗略估計是什麼 的話，沒關係，請看下方的舉例。
先用個生活上的範例來舉例。
今天和朋友出國玩耍，免不了的一定會好奇一下對方帶了多少錢，所以就問說：「誒誒誒，你們這次出來玩，帶了多少錢啊？」
小城說：「 差不多 2萬。」
小春說：「 2萬 3千 512元！」
從上面的例子來說，一般人應該會覺得小春回答的答案有點奇怪，太過精確了，其實提問者只想要知道大概的情況，聽到太精準還會覺得有點奇怪呢。
只想要知道大概的情況，就是漸進函數的精神！
如果還是不太理解我們再看一個例子。
下方為Insertion Sort的時間複雜度。
Worst Case： T(n) = a n² + b n + c （ 其中 a, b, c 皆為常數 ）
老闆比爾問說：「最近專案使用的 Insertion sort，時間複雜度為多少？」
小澤豪不猶豫地說：「n²」
小御自信滿滿的說：「an² + bn + c」
其實兩個答案都是對的，只是如果像小御一樣回答得這麼精確，就會像前一個例子，小春回答有相同的感覺，有點太多餘了。
而漸進函數的出現就是想要粗略的預估演算法所花費的時間。
最後一個是我之前常常出現的問題
老師出的考卷：請問 4n³ + 98n² – 20n + 14，請算出其 Θ()為多少？
這題多數人可能很快就會在答案卷上面寫：Θ(n³)。
如果是我的話，可能靠著之前練習題目所培養的手感，毫不猶豫填入 n³，但是其實不太清楚為什麼會寫這個答案，下次只要題目變個形式又會出錯了。
所以就讓我們擺脫之前似懂非懂的狀態，來真正理解其中的意涵吧！
首先，我們先來介紹一下這些符號
因為這些符號在演算法中佔有十分重要的地位，若行有餘力，請好好將這些符號的定義記起來（多寫幾遍差不多可以記住了，因為每個符號間的關係只有些微的差異），在未來解題時會是個有效的工具！
定義這些符號時，會有些枯燥，還請各位讀者心平氣和地把它看完。
2. 各個漸進符號的介紹 （Big-O, Omega, Theta, Little-O, Little-Omega）
1). 𝑂 (g(n))：Big-O notation（上界）
我們最熟悉的Big-O，中文的角度可以說他是該函數的寬鬆的上界。其定義如下（看到英文，不要害怕，在下一張的圖片有附上自己轉換的中文定義，可以搭配著看）：
注意！！上圖中的等號，代表的是 is 的意思，
而非數學中「等於」的概念。
f(n) = 𝑂 (g(n))
中文：g(n)是 f(n)的上界 ，或是，f(n)的上界函數是 g(n)
英文：g(n) “is” an upper bound of f(n)
看完圖片可能會產生的疑問：
1. 為什麼是 0 <= f(n)？
Ans: 因為我們的 f(n)代表的是演算法的執行時間（個人偏好想成「執行步驟」），常理說是不可能會出現「負」的執行步驟才是。其中 n代表的是 輸入的資料個數，也不可能會出現「負」的資料個數。
2. n0是什麼？
Ans: 由上圖來看，我們有兩個函數( f(n), c*g(n) )，他們有兩個不同的圖形，從圖上來看在臨界點之前，f(n) > c*g(n)；而在臨界點後，Big-O的定義才開始恆成立，而那些位於臨界點之後，皆可成為 n0。＊可以想成只有在 n0成立的條件下，「定義」才會成立！！
3. g(n)是什麼？
Ans: g(n)可以想成是符合那些定義條件中的某個代表。（看完以下範例後，最後有作個解釋）4. c * g(n)中的 c是什麼？
Ans: c是 const（常數）可以想成是為了成為代表，需要多加配件來鞏固自己的地位。（看完以下範例後，最後有作個解釋）
直接用例子來看：
Example:
1000n^2 + 100n - 6 = O(n^2)
以剛剛的範例來看，我要找的g(n)只要符合定義要的條件即可。可想而知，g(n)一定不可能只會有一個，還可能會有n³, n⁴等等，比f(n)大的函數，大有人在，而我們所選的g(n)，只是從茫茫人海中找一個出來罷了。（所以在這邊稱選到的g(n)為「代表」）
下面的部分可能就不會像Big-O講得一樣詳細，因為大部分的概念都很雷同，還請各位讀者多多包涵～～
2). Ω (g(n))：Omega notation（下界）
3). Θ (g(n))：Theta notation（嚴格上下界）
4). 𝑜 (g(n))：Little-O notation（嚴格上界）
這邊的概念，是從Big-O出來作延伸，跟Big-O不同的是， Little-o的所需的條件更多。
定義一：
定義二：
如果 f(n) 是 little-o(g(n)) 的話，則當n -> 無限大，我們取兩個函數間的「比值」會趨近於0。（請參考下方圖片）＊＊用直觀一點的想法來說，如果取比值後會等於0，則代表我的f(n) < g(n)，
( g(n)的增長速度比f(n)快很多 )，也就是說，g(n)會成為f(n)的嚴格上界。
可能這邊有些人會又個疑問說為什麼用這個方法，不能也是Big-O呢？
Ans: 因為在我們先前的定義中，Big-O中有包含「等於」的概念，所以當「函數 f(n)等於 函數 g(n)」的狀態，取比值後會是一個「常數」，如此一來對嚴謹的數學來說定義不夠明確。
取極限的計算，需用到羅必達法則。
（如果對於羅必達法則還不是很熟練的朋友可以透過這次學習的機會把他了解清楚～～）
5). ω (g(n))：Little-Omega notation（嚴格下界）
這邊的概念，是從Omega出來作延伸，跟Omega不同的是， Little-Omega所需的條件更多。
定義一：
定義二：
如果f(n)是litter-omega(g(n))的話，則當 n -> 無限大，我們取兩個函數間的「比值」會趨近無限。（請參考下圖）用直觀一點的想法來說，如果取比值後會等於0，則代表我的f(n) > g(n)，
( f(n)的增長速度比g(n)快很多 )，也就是說，g(n)會成為f(n)的嚴格下界。
和剛剛相同的概念，為什麼用這個方法不能也是 Omega呢？
Ans: 因為在我們先前的定義中，Omega中有包含「等於」的概念，所以當處䱷「f(n)等於g(n)」的狀態，取比值後會是一個「常數」，如此一來對嚴謹的數學來說定義不夠明確。
如果目前對於上述的概念，還沒有很了解的話，請看我下一篇文章，這裡面比較多的應用。可以透過範例來理解這些符號之間的關係。
不知不覺已經打了這麼多了，為了不要增加各位讀者的負擔（我也好累）。各函數間比較的部分，我們下一次再來講吧。謝謝各位的閱讀～～
如有錯誤還懇請多多指教！！
在精進自我的道路上一起加油吧！
