????????算法在編寫成可執(zhí)行程序后，運行時需要消耗時間資源和空間（內(nèi)存）資源，因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的。

? ? ? ? 時間復雜度主要衡量一個算法運行的快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間，今天我們主要來講講時間復雜度。

目錄

一、時間復雜度的概念

二、大O的漸進表示法

三、常見的時間復雜度計算

---

一、時間復雜度的概念

一個算法所花的時間與其中語句的執(zhí)行次數(shù)成正比，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。

二、大O的漸進表示法

實際計算時間復雜度時，我們并不需要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。

大O符號：是用于描述函數(shù)漸進行為的數(shù)學符號。

推導大O階的方法：

1、用常數(shù)1取代運行時間中所有的加法常數(shù)。

2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。

3、如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)，得到的結果就是大O階。

另外，有些算法的時間復雜度存在最好、平均、最壞的情況。

最壞情況：

任意輸入規(guī)模的最大運行次數(shù)（上線）

平均情況：

任意輸入規(guī)模的期望運行次數(shù)

最好情況：

任意輸入規(guī)模的最小運行次數(shù)

例如，在一個長度為N的數(shù)組中搜索一個數(shù)據(jù)x

最好情況：一次找到

平均情況：N/2次找到

最壞情況：N次找到

在實際中一般情況關注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為O（N）

三、常見的時間復雜度計算

實例1：

void BubbleSort(int *a,int n)
{assert(a);for(size_t end=n;end>0;--end){int exchange = 0;for(size_t i=1;i<end;++i){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);exchange=1;}}if(exchange=0)break;}
}

該例子為冒泡排序，最好的情況為，比較完一輪（N-1次）后，發(fā)現(xiàn)就順序的，所以最好是N次。

最壞是（N*(N+1)）/2次，通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為O（N^2）.

實例2：

//二分查找
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x){begin = mid + 1;}else if(a[mid]>x){end = mid - 1;}else{return mid;}}return -1;
}

二分查找：

最好情況：中間那個數(shù)就是要找的O（1）

最壞情況：一直除2,，到只剩一個值時，要么找到了，要么找不到。

假設N是數(shù)組個數(shù)，x是最壞查找次數(shù)，N/2/2/2……/2=1

2^x=N,x=logN(logN在算法分析中表示以2為底數(shù)，N為對數(shù)，有些地方也寫成lg N）

實例3：

//計算斐波那契數(shù)列的時間復雜度
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

?運用等比數(shù)列求和公式可知，執(zhí)行次數(shù)為2^N的數(shù)量級

所以時間復雜度應為O（2^N）

實例4：

//計算階乘遞歸Fac的時間復雜度
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

時間復雜度為O（N）