【初階數據結構】—

一、前言

1、數據結構是什么？

數據結構(Data Structure)是計算機存儲、組織數據的?式，指相互之間存在?種或多種特定關系的數據元素的集合。沒有?種單?的數據結構對所有?途都有?，所以我們要學各式各樣的數據結構，如：線性表、樹、圖、哈希等

下面我們就要踏上學習數據結構的旅程了，我們這部分主要是通過C語言來學習初階數據結構，后續我們學習C++的時候，就會繼續高階數據結構和算法。

2、算法是什么？

算法(Algorithm):就是定義良好的計算過程，他取?個或?組的值為輸?，并產?出?個或?組值作為輸出。簡單來說算法就是?系列的計算步驟，?來將輸?數據轉化成輸出結果。

簡單來說，算法就是我們在程序中，為了解決一些問題，使用某些方法，然后讓其可以的得到正確的值，那么這個方法就是算法。

比如，我們要求一個數的幾次放，那么我們使用一個函數實現，然后調用這個函數，輸入一個n就是求n次方，那么其也是一種算法，我們求某些問題，其合適的算法不是唯一的。

那么可以解決問題的算法不是唯一的，那么我們遇到問題的時候，該如何選擇合適的算法呢？如何去衡量一個算法的好壞呢？有沒有啥標準衡量一個算法呢？

我們今天要學習的內容就是去衡量一個算法的好壞的。

我們通過對這個算法的時間復雜度、空間復雜度來衡量他的好壞。

3、數據結構和算法的重要性

我們前面學習C語言的時候，就經常聽到數據結構和算法，還有我們看的這么多的競賽基本都是對于數據結構和算法的競賽，我們去看招聘網站看到的相關的工作也都基本上對于算法的熟練程度都是有要求的，然后再招聘的筆試和面試中也都是必考的項目，可想而知其的重要性。

如下：

那么我們要學好數據結構和算法有沒有什么秘訣呢？要學好數據結構和算法的秘訣就是：1、死磕代碼? 2、畫圖+思考，做到這兩點想不學會都難，前面我們學習C語言的時候，畫圖的好處其實已經顯現出來了。

二、算法效率

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

1、復雜度的概念

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

時間復雜度主要衡量?個算法的運?快慢，?空間復雜度主要衡量?個算法運?所需要的額外空間。在計算機發展的早期，計算機的存儲容量很?。所以對空間復雜度很是在乎。但是經過計算機?業的迅速發展，計算機的存儲容量已經達到了很?的程度。所以我們如今已經不需要再特別關注?個算法的空間復雜度。

三、時間復雜度

在計算機科學中，算法的時間復雜度是一個函數式T(N)，它定量的描述了這個算法的運算時間，時間復雜度是衡量一個算法的時間效率，那么有同學就會問了，那么我們為啥不直接去算一個程序的運行時間呢？

1、程序的運行時間運行機器的配置都是有關系的，比如一個硬件好的機器和一個硬件一般的機器，其機器的算力就不一樣了，那么其運行時間肯定就不一樣的。

2、程序的運行時間和編譯的環境也有關系，對于同一個算法程序，用一個老版本的編譯器和一個新的編譯器在同一臺機器下的運行時間也是可能不同的。

3、程序的運行時間只能在程序寫好后運行才好測試，沒辦法咋事前就通過理論進行計算。

4、同一個程序在同一臺機器上的每一次的運行時間都會有差異。

所以我們算法的時間復雜度都是通過一個函數式T(N)來衡量的。

那么這個函數式T(N)到底是什么呢？
那么算法的時間這個T(N)函數式計算了程序的執?次數。通過c語?編譯鏈接章節學習，我們知道算法程序被編譯后?成?進制指令，程序運?，就是cpu執?這些編譯好的指令。那么我們通過程序代碼或者理論思想計算出程序的執?次數的函數式T(N)，假設每句指令執?時間基本?樣(實際中有差別，但是微乎其微)，那么執?次數和運?時間就是等?正相關，這樣也脫離了具體的編譯運?環境。執?次數就可以代表程序時間效率的優劣。?如解決?個問題的算法a程序T(N)=N，算法b程序T(N)=N^2，那么算法a的效率?定優于算法b。

下面我們通過一個例子來學習：

我們不需要知道這個函數是實現啥功能的，我們只需要求++count語句執行了多少次：

首先是第一個二層循環，其執行的次數為N^2。然后就是第二個for循環，其執行的次數為2*N。第三個循環就執行了10次，那么總的執行次數為：T(N)=N^2+2*N+10

那么通過我們之前的數學的學習，當N達到很大的時候，只有N^2對于執行次數的影響是最大的，實際我們在計算時間復雜度的時候，計算的也不是程序的執行次數。

我們想知道的是輸入N對于程序的執行次數的增長趨勢的變化的影響，也就是當N變化的時候T(N)的變化咋樣。

我們在對復雜度的表示通常使用大O漸進表示法。

四、大O漸進表示法

大O符合：是用于描述函數漸進行為的數學符號，使用大O漸進表示法后，我們不需要再將程序的執行次數很精確的計算出來，主要是推算出其影響最大的即可。

下面為大O漸進表示法的規則：

1、時間復雜度函數式T(N)中，其只保留高階項，去掉那些低階項，這是因為當N不斷變大的時候，低階項對于結果的影響基本可以忽略不計的了。

如上面的那個案例，其時間復雜度為T(N)=N^2+2*N+10，那么我們使用大O漸進表示法，那么就為：O(N^2)。

2、如果最高階項存在而且不是1，那么則除去這個項目的常數系數，這是因為當N不斷增大的時候，這個系數對于結果的影響也是微乎其微的了，那么也就可以忽略不記了。

3、T(N)中如果只含有常數項，那么我們用常數1取代其所有的加法項，不過要注意的是1并不是代表其次數為1，而是表示其輸入N對于時間復雜度的影響趨勢是1，也就是一條平行于X軸的直線，即沒有影響。

4、如果這個程序的算法的時間復雜度其會有多種情況，即其有最好的情況，平均情況，最壞的情況，那么我們就以最壞的情況為最后的結果。

五、空間復雜度

上面我們已經學習了時間復雜度，那么我們再學習另外一個衡量算法效率的東西：空間復雜度

空間復雜度也是一個函數表達式，其是對一個算法再運行過程中需要臨時開辟的空間。

有的同學可能會以為其是開辟的空間的字節數，其實不是，這是以為每個變量的大小差異不是很大，我們所學的數據類型，就是1個字節，2個字節，4 個字節，8個字節等，其差異不是很大。所以空間復雜度算的是我們需要創建的變量個數。

空間復雜度的表達方式也是使用大O表示法，那么其使用規則也是一樣的。

不過要注意的是：

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

六、練習

1、時間復雜度的練習

練習1:

上面的時間復雜度就很好計算了，我們首先求出其函數表達式T(N)，然后再使用大O表示法。

那么我們現在開始計算吧：首先第一個循環，其執行的次數是2*N，然后是第二個循環其執行次數為10，那么其函數表達式T(N)=2*N+10，然后我們使用大O表達法，先保留最高階次項，那么此時為2N，然后最高次的系數改為1，那么最終其大O表示法為O(N)。

?練習2：

那么我們還是一樣先求其函數表達式，上面的函數表達式很明顯為：T(N)=1000。那么其和N 沒有關系，那么其很明顯使用大O表示法的話就需要使用到第三條規則，將其變成1表示：O(1)。

練習3：

可以看到這個時間復雜度和我們上面的計算有點不一樣了，我們對N進行取值看看其規律：

當為2的時候，代碼的執行次數為1，當N為4的時候，那么代碼的執行次數為2，當N為8的時候，代碼執行3次......那么我們假設代碼的執行次數為x，然后我們可以得到2^x=N。那么我們可以得到x=log N 其中這個對數的底為2，那么我們這個程序的時間復雜度就是O(log N)了。

當我們遇到對數的時間復雜度的時候我們會發現，底數對于復雜度的變化趨勢影響不大，那么我們可以不寫這個底數，不同的教材間的寫法也會有差異，但是區別不大，我們的話建議使用log N的形式。

練習4：?

上面的代碼是我們前面學習C語言的時候學習的冒泡排序，那么我們來分析其時間復雜度看看：

首先我們看看其兩個循環，外層循環：end從n遞減到1，那么一個n次迭代。

然后是內層循環遍歷整個數組，比較相鄰的兩個元素，如果前面的大于后面的元素，那么就進行交換。

那么其時間復雜度會受到數組的排序受到影響：

1、最壞情況：完全倒置。

那么外層循環：還是一樣要執行n次。

內層循環：

第一輪：n-1次比較，第二輪：n-2次比較.....第n-1輪：1次比較。

那么總的操作次數為：

(n-1)+(n-2)+(n-3)+(n-4)......+1=n(n-1)/2

那么此時的時間復雜度為O(n^2)。?

最好的情況：（已經是降序）

那么外層循環執行1次。

然后內層循環遍歷那么就執行n-1次比較。

那么就直接終止了所以其時間復雜度為O(n)。

平均情況：（順序是隨機的）

那么平均需要n(n-1)/4次，那么其時間復雜度為O(n^2)。

2、空間復雜度的練習

這里的的Fac函數很明顯使用了遞歸，而且其每運行一次就要創建一個函數棧幀，然后其不繼續遞歸的條件就是函數的參數變成0，那么就是當N減到0的時候，那么這個函數的空間復雜度為N。大O表達式為O(N)。