?馬上就要進入到數據結構的學習了 ，我們先來了解一下時間和空間復雜度，這也可以判斷我們的算法是否好壞；

---

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

就是看它的算法效率

算法效率

算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度。 時間復雜度主要衡量的是一個算法的運行速度，而空間復雜度主要衡量一個算法所需要的額外空間，在計算機發展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。

---

時間復雜度?

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

---

大O的漸進表示法

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

Func?執行的基本操作次數 ：

F(N)=N^2+2N+10

但是如果N無限大呢？

N=10? F(N) = 130

N=100? F(N) =10210

N=1000 F(N)=1002010?

因此我們有以下結論：

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

假如 F(N) = 3N^2

那么3省略 F(N) = N^2?

所以 大O為O(N^2)

另外有些算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)?

例如：在一個長度為N數組中搜索一個數據x

最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到

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

---

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

?

?F(N) = 2N+10

根據公式 F(N)=N;

所以就是O(N)

?

M和N都為未知數

F(N)=M+N;

所以就是O(M+N)?

F(N)=100;

所以F(N)=1;

所以就是O(1);?

?

有最好情況下也有最壞情況下，一般我們只考慮最壞情況下?

?

二分查找的時間復雜度為O(logN）?

?

一般情況下 遞歸的時間復雜度就為 遞歸的次數*每次遞歸執行的次數?

?

這個斐波那契遞歸得畫圖分析

所以大O為O(2^N)?

?空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 。空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數。空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法

?

空間復雜度為O(1)?

因為沒有申請其他的數組，只使用了原來的數組

時間復雜度為O(N)?

因為申請了一個其他數組

?

遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間。空間復雜度為O(N)?

---