---

---

1. 算法效率

---

1.1 如何衡量一個算法好壞

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

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

---

1.2 算法的復雜度

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

---

2 時間復雜度

---

2.1 時間復雜度的概念

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

---

2.1.1 實例

我們先來看看這段代碼：

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);return 0;
}

Func1的執(zhí)行次數(shù)：F（N）= N^2 + 2*n + 10
但在實際計算時間復雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概的執(zhí)行次數(shù)即可，那么這里我們就要用到大O的漸進表示法。

---

2.2 大O的漸進表示法

大O符號（Big O notation）：用于描述函數(shù)漸進行為的函數(shù)符號。
推導大O階方法：

①: 用常數(shù)1取代運行時間的所有加法常數(shù)。
②： 在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
③： 如果最高階存在并且不是1，則去掉與這個項相乘的常數(shù)，得到的結果就是大O階。
④： 有一些算法存在最好、最壞和平均的情況，但實際中一般關注的是算法的最壞運行情況。

所以使用大O的漸進表示法以后，Func1的時間復雜度為O(N^2).
通過上面我們很容易發(fā)現(xiàn)大O的漸進表示法去掉了那些對結果印象不大的項，簡潔明了的表示執(zhí)行次數(shù)。（本質上是計算屬于那個量級）

---

2.3 常見時間復雜度計算舉例

實例1：

// 計算Func2的時間復雜度？
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

3 空間復雜度

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

---

4 常見復雜度對比

一般算法的常見復雜度如下：

---

5 結尾

本篇博客到此就結束了。如果對你有幫助，記得三連哦。感謝您的支持！！！