我們編過不少代碼，起初學習的時候我們習慣性的認為，只要代碼能正確的運行就ok啦~很少考慮代碼的優化帶來的好處。今天說一下影響代碼性能的兩個重要指標--時間復雜度&空間復雜度。

時間復雜度：就是函數（指數學中的函數），具體執行的操作次數。通常用漸進表達式O()來表示。

空間復雜度：對象的個數。占用的空間。

算法分析一般分為三類：最壞情況、平均情況、最好情況。

算法分析要保持大局觀，忽略掉常數，關注增長最快的表達式。

我們通常見到的算法的時間復雜度有：

斐波那契數列 （遞歸：O（2^N）非遞歸：O（N））

冒泡：O（N^2）

選擇：O（N^2）

插入：O（N^2）

這里，主要舉兩個例子加以說明：

例子1：斐波那契數列

這就是著名的斐波那契數列啦。

下面講講斐波那契數列的兩種算法，并剖析時間復雜度。

（1）遞歸算法

<span style="font-size:18px;">#include<iostream>
using namespace std;
#include<assert.h>unsigned long long Fib(long long n)
{assert(n >= 0);return n < 2 ? 1 : Fib(n-1)+Fib(n-2);
}
int main()
{cout<<Fib(5)<<endl;return 0;
}</span>

斐波那契數列的遞歸算法：由于每一步計算都調用兩次遞歸，即Fib(n-1)= Fib(n-2)+ Fib(n-3) = Fib(n-3)+Fib(n-4)+Fib(n-4)+Fib(n-5)=... ?這樣下來，就相當于二叉樹，所以其時間復雜度為O(2^N)，空間復雜度為O(N)。

（2）非遞歸算法

#include<iostream>
using namespace std;
unsigned long long Fib(long long n)
{long long s0 = 0;long long s1 = 1;long long s = 0;for(int i = 0; i < n;i++){s1 = s0+s1;s0 = s1-s0;	}return s1;
}int main()
{cout<<Fib(5)<<endl;return 0;
}

非遞歸算法只是在for循環里邊數值的相互轉換，其時間復雜度為O(N),空間復雜度為O(N)。

例子2：二分查找算法

二分查找的基本思想是將n個元素分成大致相等的兩部分，a[n/2]與data做比較，如果data=a[n/2],則找到data,算法中止；如果data<a[n/2],則只要在數組a的左半部分繼續搜索data,如果data>a[n/2],則只要在數組a的右半部搜索data.

（1）非遞歸算法

int BinaryFind(int arr[],int size,int data)
{int left = 0;int right = size-1;while(left <= right)        //區間[]{int mid = left-(left-right)/2;if(arr[mid] > data){right = mid-1;}else if(arr[mid] < data){left = mid+1;}else{return mid;}}

<span style="white-space:pre">	</span>return -1;
}
int main()
{int arr[] = {1,3,5,7,9};int size = sizeof(arr)/sizeof(arr[0]);cout<<BinaryFind(arr,size,5)<<endl;return 0;
}

說起二分查找的非遞歸算法，我們還有另外一種實現。(要特別注意)

int BinaryFind(int arr[],int size,int data)
{int left = 0;int right = size;          //區間[)while(left < right){int mid = left-(left-right)/2;if(arr[mid] > data){right = mid;}else if(arr[mid] < data){left = mid+1;}else{return mid;}}

<span style="white-space:pre">	</span>return -1;
}
int main()
{int arr[] = {1,3,5,7,9};int size = sizeof(arr)/sizeof(arr[0]);cout<<BinaryFind(arr,size,5)<<endl;return 0;
}

while循環循環的次數就是時間復雜度，即時間復雜度為O(LgN)，空間復雜度為O(N)。

（2）遞歸算法

int BinaryFind_R(int arr[],int data,int left,int right)
{if(left <= right)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>int mid = left-(left-right)/2;
<span style="white-space:pre">		</span>if(arr[mid] > data)
<span style="white-space:pre">			</span>BinaryFind_R(arr,data,left,mid-1);
<span style="white-space:pre">		</span>else if(arr[mid] < data)
<span style="white-space:pre">			</span>BinaryFind_R(arr,data,mid+1,right);
<span style="white-space:pre">		</span>else
<span style="white-space:pre">			</span>return mid;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>else
<span style="white-space:pre">		</span>return -1;
}
int main()
{int arr[] = {1,3,5,7,9};int size = sizeof(arr)/sizeof(arr[0]);int left = 0;int right = size - 1;cout<<BinaryFind_R(arr,6,left,right)<<endl;return 0;
}

遞歸時間復雜度為O(LgN)。