目錄

一、算法效率

1.算法效率

1.1如何衡量一個算法的好壞

1.2算法的復雜度

二、時間復雜度

1.時間復雜度的概念

2.大O的漸進表示法

3.常見時間復雜度的計算舉例

三、空間復雜度

---

一、算法效率

1.算法效率

1.1如何衡量一個算法的好壞

long long Fib(int N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

斐波那契數(shù)列的遞歸實現(xiàn)方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？

1.2算法的復雜度

算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間(內(nèi)存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發(fā)展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關注一個算法的空間復雜度。

二、時間復雜度

1.時間復雜度的概念

時間復雜度的定義：時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數(shù)，它定量描述了該算法的運行時間。一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。
即：找到某條基本語句與問題規(guī)模N之間的數(shù)學表達式，就是算出了該算法的時間復雜度。

請計算下Func1中的++count語句總共執(zhí)行了多少次？

void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

我們可以得出Func1執(zhí)行的次數(shù)：F(N)=N^2+2*N+10

當N=10? ?F(N)=30;

當N=100? F(N)=10210;

當N=1000? F(N)=1002010;

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

2.大O的漸進表示法

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

推導大O的方法：

1、用常數(shù)1取代運行時間中的所有加法常數(shù)。
2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結果就是大O階。

有些大O的推導類似于高等數(shù)學中的取極限

就例如Func1
使用大O的漸進表示法以后，Func1的時間復雜度為O(N^2)

N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000

當N的取值非常大時我們可以省略數(shù)據(jù)中的一些數(shù)，取個大概，看著是不是類似于高等數(shù)學中的取極限

通過上面我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。
另外有些算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界)
平均情況：任意輸入規(guī)模的期望運行次數(shù)
最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)
例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到

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

3.常見時間復雜度的計算舉例

實例1：

計算Func的時間復雜度？

void Func(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

Func執(zhí)行次數(shù)表達式：F(N)=2*N+10

當N=10? ? ? ? ? ? ? ? ????????F(N)=30

當N=1000? ? ? ? ? ? ????????F(N)=2010

當N=1000000? ? ?????????F(N)=20000010

當n取很大的數(shù)值時表達式中的10可以省略，無論N乘不乘以2都是在一個數(shù)量級，也可以省略，這樣我們就得到Func的之間復雜度為N,表示為O(1)。

實例2：

計算Func的時間復雜度？
?

void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\n", count);
}

Func的執(zhí)行次數(shù)表達式為：F(N)=M+N

這里我們就要分情況討論了

情形1：當M>>N時，根據(jù)高等數(shù)學求極限的思想N可以省略

所以， 我們可以得到Func的時間復雜度為M，表示為O(M)。

情形2：當M<<N是，同理可得Func的時間復雜度為N，表示為O(N)?！?/p>

情形3：當M==N時，Func的執(zhí)行次數(shù)表達式可以表示為F(N)=2M或者F(N)=2N

Func的時間表達式為O(N)或者O(M)。

實例3：

計算Func的時間復雜度？

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

Func的計算表達式為F(N)=100

根據(jù)大O的推導1，我們可以很輕松的得到Func的時間復雜度為O(1)。

實例4：

計算strchr的時間表達式？

const char * strchr ( const char * str, int character );

庫函數(shù)strchr表示在一個字符串中查找一個字符

這道題目我們也要分情況

最好基本操作執(zhí)行一次，所以時間復雜度為O(1)

平均基本操作執(zhí)行2/N次，所以時間復雜度為O(N/2)

最壞我們要遍歷整個數(shù)組基本操作執(zhí)行N次，所以時間復雜度為O(N)。

實例5：

計算BubbleSort的時間復雜度？

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;}
}

這是一個冒泡函數(shù)時間復雜度的計算，通過前面的幾道時間復雜度的計算我們發(fā)現(xiàn)可以通過閱讀代碼計算出時間復雜度，乍一看這道題我們很難閱讀代碼獲得答案。

這里也要分情況：

情形一：所給的一組數(shù)剛好是拍好順序的，也就是最好的情況，也要進行n-1次比較，所以時間復雜度為O(N)。

情形二：所給的一組數(shù)是雜亂順序的

我們不難發(fā)現(xiàn)執(zhí)行次數(shù)是等差數(shù)列，根據(jù)等差數(shù)列的求和的到執(zhí)行次數(shù)的表達式：F(N)=n*(n-1)/2

所以時間復雜度為O(N ^2)。

實例6：

計算BinarySearch（二分法）的時間復雜度？

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;elsereturn mid;}return -1;
}

假設我們有N個數(shù)，最好的情況為執(zhí)行一次找到，最壞的情況為一直折半下去，直到剩下最后一個數(shù)字，也就是我們要找的那個數(shù)字，所以執(zhí)行次數(shù)的表達式為2^x=N，解這個表達式x=logN，所以二分法的時間復雜度為O(logN)。

ps:logN在算法分析中表示的是底數(shù)為2，對數(shù)為N。

實例7：

計算階乘遞歸的時間復雜度？

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

基本操作執(zhí)行了N次，時間復雜度為O（N）。

總結：遞歸算法時間復雜度是多次調(diào)用的累加

實例8：

計算斐波那契遞歸的時間復雜度？

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

所以時間復雜度為O(2^N)。

三、空間復雜度

空間復雜度也是一個數(shù)學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。
空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數(shù)。
空間復雜度計算規(guī)則基本跟實踐復雜度類似，也使用大O漸進表示法。
注意：函數(shù)運行時所需要的棧空間(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。

實例1：

計算BubbleSort的空間復雜度？

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;}
}

實例2：

計算斐波那契數(shù)列的空間復雜度？

long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

實例3：

計算結階乘遞歸的空間復雜度？

long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}

答案及分析：

1. 實例1使用了常數(shù)個額外空間，所以空間復雜度為 O(1)
2. 實例2動態(tài)開辟了N個空間，空間復雜度為 O(N)
3. 實例3遞歸調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)個空間?？臻g復雜度為O(N)