## 複雜度的需求
人類需要一個客觀的指標，去判斷不同演算法的優缺點
尤其在競程，解法的優劣會影響我們的選擇，這時複雜度就很重要
在演算法所耗費的時間與空間上，我們常常會使用複雜度估算的方式
## 定義
由於真正的時間/空間花費往往會受到許多其他因素干擾(如:不同機器的規格，實作的方式等等)
所以人們換個想法採用"統計演算法步驟數量"的方式，而不是實際的時間花費
空間複雜度也是同樣的概念，其實也只是找出最大的所需儲存空間，而不是實際的空間花費
而在沒特別說明的情況下，複雜度指時間複雜度，在特別區分的情況下，複雜度還可以分成平均、最壞

## 與競程相關
很多競程的題目在資料量特別大、枚舉的情況下，暴力或是較低效率的做法並不能在時間內解出題目
而在資料量不大的情況下，其實複雜度過高也沒關係，因為通常是比較簡單的題目，或是考你實作細節
關於平均、最壞複雜度的討論，在競程當中都是以最壞去判定效率，因為好的測資會包含最壞情況
(在較高級別的競賽，複雜度相同，也可能要考慮常數，因為差一點點可能就會影響成績)

## 使用方式
對於一個 function $f()$ 來說，它的時間複雜度通常以 $O(f(n))$ 表示
也念作 big-O(注意一定要是大寫O)，習慣上以 $n、m$ 表示資料的數量
實際上的意義為 "函式(演算法)執行的時間(演算法步驟數量)不超過 $f(n)$ 的某常數倍"
聽起來有點繞口，簡單講就是 $O(2n)$ 跟 $O(3n)$ 都是 $O(n)$ 常數可省略
常見的複雜度有: $O(1)$、$O(n)$、$O(nlog(n))$、$O(n^2)$、$O(2^n)$
總之可以整理成以下四個原則 :
* 不考慮常數倍數，因為常數倍數不計，所以 $log\ n$ 的底不重要
* 兩個函式相加減的 Big-O 為複雜度比較大的函式
* 如果某一段程式的複雜度是 $O(f(n))$ 共執行了 $g(n)$ 次，則複雜度為$O(f(n)\times g(n))$
* 一般的複雜度指的是 worst-case 的複雜度，也就是最難計算的資料所需的時間

那實際上的 big-O 有明確定義，但是在競程的角度來說，不需要特別去學習，只要會上述四個原則就好

## 演算法複雜度分析
舉實例做判斷
[這個網站](https://www.bigocheatsheet.com/)有常見的結構、演算法的複雜度，建議可以去看看

## 複雜度優化
除了改變演算法的方法之外，我們還能在原本的演算法上做修改來優化複雜度，以下是一些做法
### 避免重複計算
比如在兩個可能有重複元素的陣列 $A、B$ 當中，從 $A$ 挑出一個元素 $a$，從 $B$ 挑出一個元素 $b$
找出 $a+b=k$ 的可能有幾個，以上這個問題用最暴力的辦法，就是枚舉 $A、B$ 的元素
但是其實如果 $A、B$ 中有大量重複的元素，那重複枚舉就是浪費時間，所以我們可以做優化
我們把 $A、B$ 的元素表示成`(出現過的元素,出現次數)`，這樣相同元素只需要枚舉一次就好
### 改變窮舉對象
求出 $1 \le a,b,c \le N$，且 $a+b+c=K$ 的正整數解
在這個例子當中，如果用窮舉的方式複雜度就會是 $O(n^3)$，但是我們可以改變窮舉對象
因為我們只需要窮舉 $a,b$，剩餘的 $c$ 可以表示成 $K-a-b$，而 $c$ 在範圍內就可行
此時時間複雜度就可以降低為 $O(n^2)$

### 活用 bucket
所謂的 bucket 就是將大量的資料分類到多個"桶"中，而這些"桶"可以做相同處理
最後只要"桶"之間依序輸出完就可以了，最重要的概念就是如何分類、用空間換時間

## 複雜度陷阱
最後需要提醒各位，複雜度只是一個大概的指標
在現實的各種程式實作(非競賽)，複雜度常常會引導你進入陷阱
比如在資料量很小的情況下，某些演算法的優勢不僅不能體現出來
更可能因為難以除錯，泛用性低，各式各樣的原因導致各方面不如簡單的演算法
所以在解題的過程當中，也應該考慮看看快速地寫出一個"速度還行的演算法"
是否比花大量時間去寫/除錯"一個速度更快的演算法"更好
簡而言之在一般情況與大部分競賽，"能通過且寫起來(含除錯)快速的演算法"才是應該優先選擇的
在非競賽的方面，除非調用次數真的太頻繁，不然還是以較容易除錯、檢查和修改的演算法為主