算法（algorithm ）
是指令的集合，是為解決特定問題而規定的一系列操作。
它是明確定義的可計算過程，以一個數據集合作為輸入，併產生一個數據集合作為輸出。
一個算法通常來說具有以下五個特性：
- 輸入：一個算法應以待解決的問題的信息作為輸入。
- 輸出：輸入對應指令集處理後得到的信息。
- 可行性：算法是可行的，即算法中的每一條指令都是可以實現的，均能在有限的時間內完成。
- 有窮性：算法執行的指令個數是有限的，每個指令又是在有限時間內完成的，因此整個算法也是在有限時間內可以結束的。
- 確定性：算法對於特定的合法輸入，其對應的輸出是唯一的。即當算法從一個特定輸入開始，多次執行同一指令集結果總是相同的。
簡單的說，算法就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是算法的邏輯形式，後者是算法的代碼形式。
舉例：如何求0+1+2+3+...10000=?
- 算法1：依次相加 while do-while for
- 算法2：高斯解法：首尾相加*50 (1+10000)*10000/2 100*101/2
- 算法3：使用遞歸實現：sum(100) = sum(99)+100 sum(99)= sum(98)+99 ..... sum(2) = sum(1)+2 sum(1) = 1
評價算法優劣的依據：複雜度（時間複雜度和空間複雜度）
算法的複雜性體現在運行該算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間資源，因此複雜度分為時間和空間複雜度
時間複雜度是指執行算法所需要的計算工作量；
空間複雜度是指執行這個算法所需要的內存空間。
時間複雜度（Time Complexity)）定義
時間頻度：
一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。
但我們不可能也沒有必要對每個算法都上機測試。
一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。
一個算法中的語句執行次數稱為語句頻度或時間頻度，表示為T（n），n表示問題的規模
時間複雜度：
但有時我們想知道它變化時呈現什麼規律，想知道問題的規模，而不是具體的次數，此時引入時間複雜度。
一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，
若有某個輔助函數f(n),使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。
記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。
T(n)=O(f(n))
或者說：時間複雜度就是時間頻度去掉低階項和首項常數。
注意：時間頻度與時間複雜度是不同的，時間頻度不同但時間複雜度可能相同。
比如：某兩個算法的時間頻度是
T（n） = 100000n2+10n+6
T（n） = 10n2+10n+6 T(n) = n2
但是時間複雜度都是 T（n） = O（n2）
最壞時間複雜度和平均時間複雜度：
最壞情況下的時間複雜度稱最壞時間複雜度。一般不特別說明，討論的時間複雜度均是最壞情況下的時間複雜度。
這樣做的原因是：最壞情況下的時間複雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何更長。
在最壞情況下的時間複雜度為T(n)=O(n)，它表示對於任何輸入實例,該算法的運行時間不可能大於O(n)。
平均時間複雜度是指所有可能的輸入實例均以等概率出現的情況下，算法的期望運行時間。鑑於平均複雜度
第一，難計算
第二，有很多算法的平均情況和最差情況的複雜度是一樣的。
所以一般討論最壞時間複雜度
比如 我要求你在字典裡查同一個字，告訴我這個字在字典的那一頁。如果一頁一頁的翻，你需要多少時間呢？
最優的情況就是這個字在第一頁，
最壞的情況就是這個字是 整本字典的最後一個字。
所以即使我故意為難你，你也不會花費比找整本字典最後一個字還長的時間。
當然，此時聰明的你就會想用部首、筆畫等去查，才不要傻乎乎的一頁一頁翻，此時的你就會擇優選擇，因為此時你最壞的情況就是我給你部首筆畫最多、除部首外筆畫最多的一個超級複雜的一個字，但顯然比翻整本字典快得多。
為了進一步說明算法的時間複雜度，我們定義 Ο、Ω、Θ符號。
Ο(歐米可榮)符號給出了算法時間複雜度的上界（最壞情況 <=），比如T（n） =O（n2）
Ω(歐米伽)符號給出了時間複雜度的下界（最好情況 >=），比如T（n） =Ω（n2）
而Θ(西塔)給出了算法時間複雜度的精確階（最好和最壞是同一個階 =），比如T（n） =Θ（n2）
時間複雜度計算：
根本沒有必要計算時間頻度，即使計算處理還要忽略常量、低次冪和最高次冪的係數，所以可以採用如下簡單方法：
- 找出算法中的基本語句；
算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。
- 計算基本語句的執行次數的數量級；
- 只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，
- 可以忽略所有低次冪和最高次冪的係數。這樣能夠簡化算法分析，並且使注意力集中在最重要的一點上：增長率。
- 用大Ο記號表示算法的時間性能。
- 將基本語句執行次數的數量級放入大Ο記號中。
時間複雜度舉例：
- 一個簡單語句的時間複雜度為O(1)。
<code>int count=0;/<code>
- 100個簡單語句的時間複雜度也為O(1)。（100是常數，不是趨向無窮大的n）
<code>int count=0;/<code>
- 一個循環的時間複雜度為O(n)。
<code>int n=8, count=0;
for (int i=1; i<=n; i++)
count++;/<code>
T(n)=O(n)
- 時間複雜度為O(log2 n)的循環語句。
<code>int n=8, count=0;
for (int i=1; i<=n; i*=2)
count++;/<code>
1 2 4 8 16 32
230=1024*1024*1024 = 1000*1000*1000=10億
- 時間複雜度為O(n2)的二重循環。
<code>int n=8, count=0;
for (int i=1; i<=100n; i++)
for (int j=1; j<=10n; j++)
count++;/<code>
- 時間複雜度為O(nlog2n)的二重循環。
<code>int n=8, count=0;
for (int i=1; i<=n; i*=2)
for (int j=1; j<=n; j++)
count++; /<code>
- 時間複雜度為O(n2)的二重循環。
<code>int n=8, count=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=i; j++)
count++;/<code>
1+2+3+4....+n=(1+n)*n/2
需要複雜些數學運算：1+2+3+.....+n=(n+1)*n/2 時間複雜度是 O(n2)
後面講解查找和排序算法時會大量的設計時間複雜度，作為選擇查找和排序算法的重要依據
常用的時間複雜度級別：
- 常數階O(1)
- 對數階O(log2n)
- 線性階O(n)
- 線性對數階O(n*log2n)
- 平方階O(n2)
- 立方階O(n3)
- ...
- k次方階O(nk)
- 指數階O(2n)
- 階乘階O(n!)
上面各種時間複雜度級別，執行效率越來越低。
大家發現對數階O(log2n)和線性階O(n)的效率差異了嗎，當n=10的8次方（1億）時，執行此時一個是1億次，一個是8次。
所以編寫算法時一定要注意時間複雜度的選擇。
空間複雜度（Space Complexity)）：
算法的存儲量包括:
- 程序本身所佔空間
- 輸入數據所佔空間；
- 輔助變量所佔空間
輸入數據所佔空間只取決於問題本身，和算法無關，則只需要分析除輸入和程序之外的輔助變量所佔額外空間。
空間複雜度是對一個算法在運行過程中臨時佔用的存儲空間大小的量度，一般也作為問題規模n的函數，以數量級形式給出，記作：
S(n) = O(g(n))
- 空間複雜度分析1：
<code>int fun(int n){
int i，j，k，s;
s=0;
for (i=0;i<=n;i++)
for (j=0;j<=i;j++)
for (k=0;k<=j;k++)
s++;
return(s);
}/<code>由於算法中臨時變量的個數與問題規模n無關，所以空間複雜度均為S(n)=O(1)。
- 空間複雜度分析2：
<code>void fun(int a[]，int n，int k) {
//數組a共有n個元素
int i;
if (k==n-1)
for (i=0;i printf(“%d\\n”，a[i]); //執行n次
else {
for (i=k;i a[i]=a[i]+i*i; //執行n-k次
fun(a，n，k+1);
}
} /<code>此屬於遞歸算法（後續講解），每次調用本身都要分配空間，fun(a,n,0)的空間複雜度為O(n)。
注意：
- 空間複雜度相比時間複雜度分析要少
- 對於遞歸算法來說，代碼一般都比較簡短，算法本身所佔用的存儲空間較少，但運行時需要佔用較多的臨時工作單元；
- 若寫成非遞歸算法，代碼一般可能比較長，算法本身佔用的存儲空間較多，但運行時將可能需要較少的存儲單元。
閱讀更多 極客蕭 的文章
