一個理論的成立，通常也會帶動相關技術的進步。所以我們今天將利用昨天學的漸進符號，反過來改進我們實際在估算複雜度的流程。
昨天在最後提到了兩個問題：
因為以上兩點並非理論層面的問題，而是理論有點與現實脫節而產生的疑惑，所以我們今天將從實際的程式著手討論
int sum(int array[], int n) {
int result = 0;
for (int i = 0; i < n; ++i) {
result += array[i];
}
return result;
}
我們先從過去曾看過的例子開始，在以前我們是直接很粗暴地用變數對其步驟數進行計數，再觀察出複雜度函數然後 OOXX 搞一大堆。
但是現在我們已經知道了其實步驟數不必估計的太精確，只要量級一樣即可。因此我們可以先單獨估計每個指令步驟數的漸進複雜度，然後做加總後再取一次漸進複雜度就可以了。
口說無憑，實際操作一次吧！
int sum(int array[], int n) {
int result = 0; // Θ(1)
for (int i = 0; i < n; ++i) { // Θ(n)
result += array[i]; // Θ(n)
}
return result; // Θ(1)
}
其中第一個和最後一個指令是 很直觀，不過為什麼 for 迴圈那行是
？因為它被執行了
次，不過就算它執行的次數是
、
還是多少，其 Big Theta 都是一樣的，這在昨天已充分練習過了。
加總後 ，因為相加的都已經是漸進複雜度了，它們基本上就代表了不同的量級。
因此按照定義，較小的量級相對於較大的量級基本上就是常數，所以只要保留最大量級作為代表就可以了。
因為我們剛剛其實也只是計算所有的指令的時間複雜度，然後再取最大量級的指令作為整段程式的時間複雜度，所以要是你已經很熟練的話，也可以直接觀察程式中那些會被執行最多次的指令，一樣將他們漸進複雜度相加即可。
以剛剛的程式為例，很明顯 result += array[i] 這行會被執行最多次，而這行執行次數的漸進複雜度就是 ，剛好就是該段程式的漸進複雜度。
因為前面幾篇幾乎都在講時間複雜度，比較少談到空間，儘管兩者概念幾乎一樣，不過這邊還是淺談一下並舉個例子。
一個程式的空間複雜度代表它運行時所占用的記憶體，而這個記憶體又有分不論輸入如何變化整體大小都不會變的固定記憶體消耗和會隨著輸入增長而變大的變動記憶體消耗，而空間複雜度一般只看變動的記憶體消耗。
void countFrequency(vector<int>& vec) {
vector<int> count(*max_element(vec.begin(), vec.end()) + 1);
for (int i = 0; i < (int)vec.size(); ++i) {
++count[vec[i]];
}
for (int &i : vec) {
i = count[i];
}
}
上面是一個將 vector 的元素換成它的出現次數的程式碼，我們又要怎麼分析它的空間複雜度呢？
一樣可以計算可變記憶體消耗的漸進複雜度，以上的程式碼中明顯 vector count 的消耗量級會隨輸入變化，為變動的記憶體消耗，且整段程式只有它是可變記憶體消耗（如果還有其他的可變記憶體消耗，則必須像上面時間複雜度那樣相加後再取漸進複雜度），因此可以用 count 的空間複雜度作為整段程式的空間複雜度。
不過它的空間複雜度的自變數是哪個呢？前幾篇在處理複雜度函數時候一下子 一下子
的，那時雖然都說
表示輸入，但是這個
到底是輸入的什麼東西呢？答案是它是一個從輸入中提取的特徵。
就好像一個加總函數 的
表示陣列元素的數量，這就是它的
；而這邊記憶體消耗看得出來就是
vec 中數值最大的元素，所以如果把「最大數值」表示成 的話，就可以將空間複雜度表達成
，不過因為是數值大小，所以其實一般會表示成
從輸入提取特徵的概念對於只有練習解題而沒有特別研究演算法的人好像會比較沒感覺（我在講以前的自己QQ），因為題目往往會事先設計好每個變數的數量和範圍，所以不需要在意輸入的特徵的問題，因此不會注意到某些特徵其實在真實世界中往往容易變得很大很難處理。
void InsertionSort(int array[], int n) {
for (int i = 1; i < n; ++i) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
--j;
}
array[j + 1] = key;
}
}
上面的程式是一個插入排序，它的原理就像我們一般在整理撲克牌一樣：假設當前處理的牌用 key 表示，且因為我們會從最左邊開始排序，所以已知 key 的左邊一定都已經排好了。此時只要從 key 左邊的牌的最右邊開始比較，當發現第一張小於等於 key 的牌就插入到它的前面。如此只要第二張以後的牌都當過一遍 key 就可以排好順序，這過程就跟玩撲克牌時整理手牌一樣。
解釋這個演算法不是此節的主要目的，想要知道詳細資訊可以參考 Comparison Sort: Insertion Sort(插入排序法)
那我們來分析看看這個演算法的時間複雜度吧！
首先，第二行的 for 迴圈以下指令的漸進複雜度是 ，這很清楚。所以裡面除了 while 迴圈以外的指令都是
，好了！那麼 while 迴圈的 Big Theta 是什麼呢？
是不是注意到了呢？內部 while 迴圈每次的執行次數是不固定的，因此你沒辦法輕易的看出它的確切的量級。與其說不固定，不如說它在不同的輸入下會有不同的表現，以下我們來分兩個 case 來分析：
[1, 2, 3, 4 ,5] ，這種情況下可以發現每次的 key 遇到的元素都會小於它，因此 while 根本進不去，while 迴圈變成 [5, 4, 3, 2, 1] ，這種情況下可以發現每次的 key 遇到的元素都會大於等於它，因此 while 進去後一定會跑到 j == -1 ，此時的 while 迴圈變成 有沒有發現本來都用 Big Theta，但在第二個 case 卻改成用 Big O？這是因為儘管我知道第二個 case 一定會跑到底，但每一輪的 key 左邊的元素數量都不一樣，因此我沒辦法輕易的斷定它的上界下界都剛好等於 ，但我能保證它的上界是
。
這就是電腦科學家、數學家要設計那麼多漸進符號的理由之一，因為我們不能保證我們時時刻刻都能完美找到剛好符合上下界的量級，就像此時只找上界才是比較好的做法一樣。
事實上，一般在表示它都會分成三種狀況來表示：
best case 和 worst case 剛剛討論過了，但 average case 怎麼來的呢？老實說這需要仰賴有點複雜的數學機率證明， 雖然我不是數學家，但這聽起來挺難得對吧？ 因此這邊會省略掉證明。
對證明有興趣的人可以去看 Average Case Analysis of Insertionsort
但實際上我們究竟要用哪個 case 來評估這個排序演算法的時間複雜度呢？
[資訊之芽 算法班] 01. 複雜度分析 影片中做過一個非常生動的比喻：假設極限運動跳傘的降落傘有 的故障率，你是運動員的話你仍然會期望那
的故障發生後還是有機率能保住一條命。
在這邊也是一樣的，我們往往都會關注最糟的情況，即使那最糟的狀況非常罕見也一樣，也因此我們較常用的漸進符號是 Big O，因為它代表一個糟糕的上限。
不過即使這樣，這個插入排序的 best case 是 還是有它的價值的！例如假如有另外一個叫做快速排序的排序演算法可以很有效率地把陣列的數「分組」，使得較大的數一定能跑到後面的組別、較小的數一定能跑到前面的組別，組別間已排序完成，但不保證組內是否排序。
此時對於組內使用插入排序就非常適合，因為在較小的範圍內 不痛不癢，且因為每個組別內都是相近的數，它們是已排序的機率較高，因此在組別內部的排序使用插入排序效率可能會比全程用快速排序更有效率。
因此就有人發明所謂的混合算法 Hybrid algorithm ，就是將兩種或更多種其他演算法組合在一起以解決同一個問題的演算法，通常這麼做是因為不同演算法應對不同 case 的效率不同，所以只要針對不同狀況對症下藥，就可以得到比套用單一演算法還要更好的效率！
C++ std::sort 就是使用一種被稱為 introsort 的 Hybrid algorithm ，是結合了 quicksort + heapsort + insertionSort 的演算法合成獸。
要是很好奇 introsort 是怎麼實作的，可以參考下面三個網址：Introsort Algorithm – Overview and C++ Implementation 、 Introsort – C++’s Sorting Weapon 、 IntroSort
至此基本的時間複雜度觀念已經說得差不多了，之後預計是會先介紹一些分析時間複雜度的手法和技巧，再介紹關於複雜度理論更深入的一些知識，請各位敬請期待！
iThome鐵人賽
看影片追技術