# 前言
* [演算法競賽是甚麼?](https://hackmd.io/@LittlePants/Hyw_rueGK)

首先，透過演算法競賽可以特選或是保送到你心目中的大學是非常難的，如果你想靠這條路升學，請三思，並祝你幸運。

選手的培訓大多靠學長姐帶領，或是網路上的資源，但是演算法更新快，近幾年由於政府的推動也有許多人加入，這條路非常難走，因此資訊讀書會的目標僅是讓多數學員可以有基礎程式設計的基礎(約APCS3級分)，並讓想要學到更多東西的人有教材或資源可以用，總而言之，只有分外努力，才可以使成功顯得毫不費力，如果你真的想要學的深，最好的方法就是多練，這條路沒有捷徑。

## 如何估算複雜度
為了評估程式的執行效率，我們可以測量時間

複雜度通常以$O(f(n))$表示 O通常被稱為大O符號，$n$是資料量，而$f(n)$是$n$的函數

* 時間複雜度

| Big O Notation | 別名 | 常見演算法 |
| -------- | -------- | -------- |
| $O(1)$ | 常數 | 陣列讀取 |
| $O(n)$ | 線性 | [Linear search](https://en.wikipedia.org/wiki/Linear_search)|
| $O(logn)$ | 對數(Logarithmic ) | [二分搜尋法](https://en.wikipedia.org/wiki/Binary_search_algorithm)|
| $O(nlogn)$ | 線性 | [堆積排序](https://hackmd.io/@SupportCoding/Heap_sort)，[合併排序](/Merge_sort) |
| $O(n^2)$ | 平方 | [氣泡排序](https://en.wikipedia.org/wiki/Bubble_sort)，[插入排序](https://en.wikipedia.org/wiki/Insertion_sort)|
| $O(n^3)$ | 三次方 | 三重迴圈枚舉法，高斯消去法求解線性方程組 |
| $O(2^n)$ | 指數 | 費氏數列 |
| $O(n!)$ | 階層 | 排列組合，八皇后問題 |


通常一秒能執行的量大概是$O(10^9)$
因此我們可以得到下表

----

| $n$大小 | 通常使用甚麼方法 |
| -------- | -------- |
| $n>10000$ | $O(n)$ or $O(nlog(n))$|
| $n>1000$ | $O(n^2)$ |
| $n>100$ | $O(n^3)$ |
| $20<=n<=26$ | $O(2^n)$ |
| $n=<10$ | $O(n!)$ |