---

一、數據結構前言

1.1 數據結構

數據結構就是計算機存儲、組織數據的方式，是相互之間存在一種或多種特定關系的數據元素的集合。大多數數據結構的用途都有自己的特性。常見的數據結構有：線性表、樹、圖、哈希等

1.2 算法

我個人認為，算法算法，即是一種解決問題的方法，在計算機中算法就是取一個或一組的值為輸入，并產生一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數據轉化成輸出結果。

---

二、算法效率

這里以一道力扣題來體現算法的效率
輪轉數組


超出時間限制便是算法效率不夠的原因，代碼是正確的，但當給的數組數據很多的時候，就需要機器處理很長時間才能得出結果，這里就牽扯出了一個概念：復雜度

2.1 復雜度的概念

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

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

我個人認為這也是現在游戲優化普遍做的比較一般的原因

---

三、時間復雜度

定義：在計算機科學中，算法的時間復雜度是一個函數式T（N），這個函數式子就類似于數學中的函數f（x）=ax+b，其圖像是一個值的變化趨勢，函數式子T（N）也是如此。它定量描述了該算法的運行時間。時間復雜度是衡量程序的時間效率，那為什么不直接去計算程序的運行時間呢？

1. 因為程序運行時間和編譯環境和運行機器的配置都有關系，比如同一個算法程序，用一個老編譯器進行編譯和新編譯器編譯，在同樣機器下運行時間不同。
2. 同一個算法程序，用一個老低配置機器和新高配置機器，運行時間也不同。
3. 并且時間只能程序寫好后測試，不能寫程序前通過理論思想計算評估。

這個T（N）函數式計算了程序的執行次數。算法程序被編譯后生成二進制指令，程序運行，就是cpu執行這些編譯好的指令。我們可以通過程序代碼或者理論思想計算出程序的執行次數的函數式T（N），假設每句指令執行時間基本一樣（實際中有差別，但微乎其微），那么執行次數和運行時間就是等比正相關，這樣也脫離了具體的編譯運行環境。執行次數就可以代表程序時間效率的優劣。比如解決一個問題的算法a程序T（N）=N，算法b程序T（N）=N²，那么算法a的效率一定優于算法b

案例1：

通過對N取值分析，對結果影響最大的一項是N²,這是為什么呢？這里的O又是什么？
實際中計算時間復雜度時，計算的也不是程序的精確的執行次數，精確執行次數計算起來還是很麻煩的（不同的一句程序代碼，編譯出的指令條數都是不一樣的），計算出精確的執行次數意義也不大，因為我們計算時間復雜度只是想比較算法程序的增長量級，也就是當N不斷變大時T（N）的差別，上圖可以看出當N不斷變大時，常數和低階項對結果的影響很小，所以只需要計算程序能代表增長量級的大概執行次數，復雜度的表示通常使用大O的漸進表示法

3.1 大O的漸進表示法

大O符號：是用于描述函數漸進行為的數學符號

推導大O階規則

1. 時間復雜度函數T（N）中，只保留最高階項，去掉那些低階項，因為當N不斷變大時，低階項對結果影響越來越小，當N無窮大時，就可以忽略不計了。
2. 如果最高階項存在且系數不是1，則去除這個項目的常數系數，因為當N不斷變大，這個系數對結果影響越來越小，當N無窮大時，就可以忽略不計了。
3. T（N）中如果沒有N相關的項目，只有常數項，用常數1取代所有加法常數

3.2 時間復雜度計算示例

3.2.1 示例1

3.2.2 示例2

T（N）里的N不代表任何后面的任何變量，這里的N既可以指代M，也可以指代N

3.2.3 示例3

3.2.4 示例4

這串代碼的意思是在字符串中查找指定的字符，查找到直接返回，沒有查找到繼續查找，遍歷到字符串結尾還沒有找到，返回NULL

這里若要查找e的話，循環一次，是個常數，所以T（N）=1
若要查找r的話，循環N-2次，所以T（N）=N
若要在中間查找一個字符，則循環N/2次，所以T（N）=N/2

總結：
通過上面可以發現，有些算法的時間復雜度存在最好、平均和最壞的情況
最壞情況：任意輸入規模的最大運行次數（上界）
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數（下界）
大O的漸進表示法在實際中一般情況關注的是算法的上界，也就是最壞運行情況

3.2.5 示例5

外層循環從n到1，循環n次，內存循環從1到n/n-1/… 一直到1，內存循環循環多少次不確定。外層循環n次毋庸置疑
所以這里需要分情況討論
因為外層循環固定n次，把這n次內層循環的次數累加起來，就得到了總的循環的次數
這里看每一次，第一次end=n，第一次內層循環進來，i<n，i的變化1到n-1，循環n-1次
第二次end- -，i<n-1，i的變化為1到n-2，循環n-2次
當第n次，也就是當最后一次end為1，內層循環i<1，條件不滿足，循環不執行
end為2時，也就n-1次，內層循環還會循環一次

剩下如圖中所寫。

3.2.6 示例6

這里隨著n的變化，循環次數也在發生變化，然而并不是n是多少，就循環次數是多少
這里與前面執行次數求解不同的原因是cnt不是+1而是×2

這里時間復雜度的寫法看似不對，以2為底怎么能不寫呢，實則是當n接近無窮大時，底數的大小對結果影響不大。因此，一般情況下不管底數是多少都可以省略不寫，即可以表示為log n
不同書籍的表示方法不同，但寫法差別不大

3.2.7 示例7

調用Fac的次數等于遞歸的次數，這里要把每次遞歸進行函數調用的時間復雜度累加起來
遞歸是從N-1開始的，N-1到0，遞歸了N次

上面就是所有常見時間復雜度的推理了，雖然有些算法的時間復雜度的推理可能很復雜，但以上這些一般在筆試面試的時候已經夠用

---

四、空間復雜度

空間復雜度也是一個數學表達式，是對一個算法在運行過程中因為算法的需要額外臨時開辟的空間。

空間復雜度不是程序占用了多少bytes的空間，因為常規情況每個對象大小差異不會很大，所以空間復雜度算的是變量的個數。

空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法

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

4.1 空間復雜度計算示例

4.1.1 示例1

函數棧幀在編譯期間已經確定好了，只需要關注函數在運行時額外申請的空間。BubbleSort額外申請的空間有exchange等有限個局部變量，使用了常數個額外空間

因此空間復雜度為O（1）

4.1.2 示例2

Fac遞歸調用了N次，額外開辟了N個函數棧幀，每個棧幀使用了常數個空間，因此空間復雜度為O（N）

當再動態內存開辟了n個大小的空間時，單詞遞歸的空間復雜度也為N了，空間復雜度就為O（N²）

單獨動態內存開辟n個大小的空間時，空間復雜度也為O（N）

---

五、常見復雜度對比

隨著復雜度增大，程序性能是越差的

---

六、復雜度算法題

6.1 旋轉數組

再看剛剛的題

這道題外層循環k次，內層是numsSize-1變化到1，循環numsSize-1次，模糊認為循環numsSize次，所以認為時間復雜度為O（K*numsSize），K和numsSize均為變量

題目給出二者關系：二者一樣大，所以可以認為每個變量時間復雜度為n，這里用n替換了所有的變量，有時不知道兩個或多個變量多大，均視為一樣大

所以這道題的時間復雜度為O（n²）,空間復雜度為O（1），因為代碼中沒有額外開辟空間。
時間復雜度太高了，超出時間限制

所以改進的思路也就有了，下降時間復雜度就可以，第一次代碼使用了循環嵌套，所以時間復雜度為n²，改進代碼就不用循環嵌套，用兩次循環，時間復雜度就是O（n）

第一次代碼改進就是額外開辟一個和原數組大小一樣的空間

直接對比原數組和輪轉后的數組可以將數組最后k個數據挪到最前面，剩下的數據依次放后面。

這里i來定位原數組的下標，i+k定位新數組的下標，依次把1，2，3，4放到新數組之后，原數組i到了下標為4的位置，此時新數組下標i+k=4+3=7，越界了，這里原數組5要往下標為0的位置放，這里就使用圖中的取余，也不會影響前面數據的存放。

該優化算法因為額外開辟的新的空間，所以空間復雜度為O（n），時間復雜度也為O（n），是用空間換時間的一種常見改進思路

再說一種更好的改進思路，既減少了時間復雜度，也不會增加空間復雜度

只需要設計一個函數，來完成逆置的操作即可，想使用的時候隨時調用，只要將下標的范圍傳過去就可以了，范圍的下標分別稱為left和right


一般來說正確的思路如圖，然而卻給出了越界的報錯

出現越界的用例如圖：數組中只有一個數據-1，但其輪轉了兩次，就是重復輪轉
這里調用函數，numsSize-k-1=1-2-1=-2，此時left=0，right=-2，沒有進入循環，所以第一次調用沒有出現報錯，緊接著第二次調用numsSize-k=-1，numsSize-1=0，進入循環int tmp=nums[left]，沒有-1這個下標，所以溢出了。

所以這里要對k進行特殊處理，首先要理解
當向右輪轉 數組元素個數（即 n 次） 時，相當于每個元素都繞了一圈，又回到最初位置 。比如這個列表 [1,2,3,4,5,6,7] ，元素個數 n = 7：

輪轉 1 次后：[7,1,2,3,4,5,6]
輪轉 2 次后：[6,7,1,2,3,4,5]
……
輪轉 7 次后，每個元素都剛好轉了一圈，又回到初始的 [1,2,3,4,5,6,7] ，所以看起來 “數據不變” 。
而比如說這里numsSize=7，k=14，7個元素輪轉14次還是不變的。
就可以加這樣一句代碼：

這里沒有開辟新的空間，所以空間復雜度為O（1），只使用了一次循環，所以時間復雜度為O（n）

---

總結

以上就是數據結構復雜度的全部內容了，有一說一暑假自律還是有些難度的，喜歡的兄弟們不要忘記一鍵三連給予支持~