數據結構概述和時間空間復雜度

1. 什么是數據結構

數據結構（Data Structure）是計算機存儲、組織數據的方式，指相互之間存在一種或多種特定關系的數據元素的集合。

2. 什么是算法

算法（Algorithm）就是定義良好的計算過程，他取一個或一組值最為輸入，并產生一個或一組值作為輸出。簡單來說就是一系列的計算步驟，用來將輸入的數據轉化成輸出結果。

3. 算法效率

算法在編寫成可執行程序后，運行需要耗費時間資源和空間資源。因此衡量一個算法的好壞一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。

時間復雜度主要衡量一個算法的快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經計算機行業的迅速發展，計算機存儲容量已經到達了很高的程度。所以我們如今不太需要太過于關注一個算法的空間復雜度（但是大的離譜的情況還是要注意一下的）。

4. 時間復雜度

4.1 時間復雜度的概念

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法運行起來的時間。一個算法執行所耗費的時間，從理論上來說，是算不出來的，因為每次計算的時間都與計算機的性能和輸入的數據的復雜程度有關。所以為了分析算法耗費的時間，就有了時間復雜度這個分析方式。一個算法所消耗的時間與其中的語句執行次數成正比，算法中的基本操作的執行次數，為算法的時間復雜度。

即：找到某條基本語句與問題規模N之間的數學表達式，就是算出了該算法的時間復雜度。

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執行的基本操作次數：$F(N)=N^2+2?N+10$

• N = 10 F(N) = 130
• N = 100 F(N) = 10210
• N = 1000 F(N) = 1002010

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

4.2 大O的漸進表示法

大O符號（big O notation）：是用于描述函數漸進行為的數學符號。

推導大O階方法：

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

上面的$F(N)=N^2+2?N+10$使用大O階漸進表示法以后就是：$O(N^2)$。

另外，一個算法的時間復雜度可能存在最好、平均、最壞三種情況：

• 最壞情況：任意輸入規模的最大運行次數（上界）。
• 平均情況：任意輸入規模的期望運行次數。
• 最好情況：任意輸入規模的最小運行次數（下界）。

在實際中一般情況關注的是算法的最壞運行情況。

5. 空間復雜度

空間復雜度和時間復雜度類似，也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度。

空間復雜度不是程序占用了多少比特的空間，而是變量的個數，空間復雜度的計算規則和時間復雜度類似，也使用大O漸進表示法。

函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候顯式申請的額外空間來確定。

6. 常見的復雜度對比

復雜度表達式	大O漸進表示法	數量級
$5201314$	$O(1)$	常數階
$3N+4$	$O(N)$	線性階
$3N^2+4N+5$	$O(N^2)$	平方階
$3lo{g}_{2}N+4$	$O(logN)$	對數階
$2N+3lo{g}_{2}N+14$	$O(NlogN)$	NlogN階
$N^3+2N^2+6$	$O(N^3)$	立方階
$2^n$	$O(2^N)$	指數階