數據結構篇：空間復雜度和時間復雜度

1.前言：

?1.1 學習感悟

?1.2 數據結構的學習之路(初階)

2.什么是數據結構和算法

2.1 數據結構和算法的關系

2.2 算法的重要性

2.3 如何衡量算法的好壞

3.時間復雜度

3.1 時間復雜度的概念

3.2 大O的漸進表示法 O()

4.空間復雜度

5. 常見的時間復雜度和空間復雜度計算

5.1 時間復雜度計算

5.2 空間復雜度計算

6.時間復雜度對比圖

7.結語

1.前言：

? ? ? ? 1.1 學習感悟

????????本篇文章作為數據結構的開篇，也是對C語言部分結尾的繼承，屬于是承上啟下，數據結構中目前使用的編譯器還是Visual Studio 2022，在正式講之前，說點篇外話，繼上一篇動態內存的管理后，很久沒有更新是因為博主的電腦出了問題，維修了小半個月，再者本人對于數據結構的學習周期比較長，數據結構的難度也相對于C語言高了一個層次，但是我覺得只要認真努力的學下去，武裝自己，然后做對題目，那一刻，先前再怎么苦也值得！當你做對題目，在網站上提交你的代碼通過的時候，肯定會有滿滿的成就感，不是嗎？

? ? ? ? 1.2 數據結構的學習之路(初階)

????????在數據結構的具體學習中，大致分為有：

對于時間復雜度和空間復雜度的一個基本了解
順序表
鏈表
棧
隊列
二叉樹
排序

????????這7大類，數據結構基礎篇主要內容就是這些，包括想要考研的朋友們，王道計算機408中的數據結構中，是線性表（順序表，鏈表），棧，隊列，數組，串，二叉樹，查找，排序。大部分都能包含。如果想要考研的同學看到文章也有一絲絲的收獲，這對我也是很大的鼓舞。在這里，我也不能說數據結構怎么學能學好，我也是在學習的過程中，但是經過了一段時間的初步學習，我認為有三點必須要做到，這樣學數據結構不能說萬無一失，只能說會學的很扎實，思路很順暢，時間相對花的少很多。

多畫圖，對于每個內容的學習都盡量畫圖，它能幫助你很好的構思代碼的整體流程，甚至能夠潛在地培養自己的算法素質，算法能力。
多調試，在C語言學習過程中，應該都是能夠學會如何基本的調試，這里就不過多贅述了，想了解基本方法請移步C語言初階回顧-CSDN博客中有過相關介紹，在初步學習的時候可能會不重視調試，覺得我去百度一下，或者把自己的代碼截圖，復制給AI工具，（文心一言，deepseek）讓著幫忙解析就好了，這是個方法，但不是最好的方法，ai會讓你養成惰性，如果你學會了怎么去調試，那是自己成長的一步，如果再進一步，大部分由于疏忽導致的錯誤能夠通過你親手F10，F5，F11出來解決，那是一件多么舒服的事情，你可以通過自己而不是外部工具去解決，久而久之，你會愛上調試的，會出了bug第一時間不是想AI幫我一下，而是下意識F10，調試是一個基本功！在數據結構的學習中，調試是必不可少的，也是和畫圖同等重要的能力。
了解函數棧幀空間，這在二叉樹的學習中，是一個門檻，如果了解了函數棧幀的相關知識，學起來將事半功倍。像博主本人在學習的過程中，把那一塊知識淡忘了，就會重新去溫故一下，看看曾經寫過的文章，從而知新。忘記正常，記起來就好了。

????????進入正題

2.什么是數據結構和算法

? ? ? ? 在互聯網中，各大社交平臺都在討論數據結構的時候，總會和算法緊密相連，而且我看到過很多互聯網大廠和中廠，算法崗位的學歷起步是要碩士。算法要求之高，那么到底什么是數據結構，什么又是算法。這兩者為什么緊密相連？

2.1 數據結構和算法的關系

????????數據結構，在博主的看來，就是電腦在內存中對存儲數據有不同的結構方式。而算法，就是解決一個或者多個問題的一系列計算步驟，用來把輸入的數據轉化為自己想要結果。所以算法我認為不單單是一種解決問題的方式，更多的還是思維。

????????而算法和數據結構的關系可以理解為互相的關系，數據結構給算法提供發揮作用的空間，算法為數據結構進行作用。沒有數據結構，算法發揮不出它的作用，沒有算法，數據結構就沒有問題的解決這一步，兩者共生。我在網絡上也搜到我認為很不錯的觀點，大家可以看看：

2.2 算法的重要性

?2.3 如何衡量算法的好壞

? ? ? ? 算法在對問題解決的過程中，或者說在計算機中運行的時候，是要消耗內存資源和空間的。以及要花費一定時間。那這里其實已經指出了衡量算法優劣的兩個標準，這也是面試官常考的點：

? ? ? ? 1.時間復雜度

????????2.空間復雜度

? ? ? ? 不知道你們有沒有發現一個現象，或者看到這里想起來一些東西。在c語言的遞歸中，比如斐波那契數列，階乘遞歸，一開始數字小還好，但當你輸出一個較大的數字，斐波那契數列的第40，45，50，越往后計算機算的就越慢，而且打開任務管理器觀察，運行該程序所占用的內存百分比會只多不少。?我以斐波那契數列來實測一下。

#include<stdio.h>int Fib(int n)
{if (2>=n){return 1;}else{return Fib(n - 2) + Fib(n - 1);}
}
int main()
{int a = 0;scanf("%d",&a);int ret =Fib(a);printf("%d\n",ret);return 0;}

? ? ? ?輸入的值為30時：速度很快，瞬間出來。

時間復雜實測

? ? ? ?輸入值為40時：?出來了，過了5秒，光標在閃動（由于博主嘗試錄屏，但是無法錄制到cmd框，就不能放出視頻演示了，手機錄制效果不好，大家自行嘗試）

????????

? ? ? ? ?輸入的值為45時，大概過了半分鐘，才出結果，數字也確實非常大。

?????????說明用遞歸這個算法來解決斐波那契數列，數字大了，并不好，用for循環，會更好。計算時間就表示時間復雜度，內存資源的消耗就表示空間復雜度。那也不能每次都上機實測，所以就有了這兩個概念。

3.時間復雜度

? ? ? 3.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 A = 10;while (A--){count++;}

? ? ? ? 上述過程中，在第一個for循環中，嵌套了一個for循環，那么在里面的執行次數，以未知數x來表示，就是,第三個for循環是單獨的，是2，第三個就是常數10了，總次數是,但是真心要算出來嗎，未知數小還好，x=1001，2345，54233這些復雜的數字，算起來未免過于繁瑣。實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數。那么這里我們使用大O的漸進表示法。

3.2 大O的漸進表示法 O()

????????在我的筆記中是這樣的記載的：

用常數1取代運行時間中的加法常數
保留最高階項即可
最高階次方不是1的話，把這個項的相乘系數刪了。

????????所以上面的表達式去掉常數，去掉非最高階，就剩個了，那么規范的糾正我的錯誤，我剛剛是用數學表達式來寫，正確的應該是把x換成N，所以是。

????????通過上面大O的漸進表示法去掉了那些對結果影響不大的項，表示出了執行次數。另外有些算法的時間復雜度存在最好、平均和最壞情況：你選擇哪個？

????????這里舉個生活中的例子就明白了，你和你最好的朋友聚餐，或者工作有個重要的客戶要約見，然而你手中的活還沒干完，對方給你了下午5點，晚上7點和8點見面，你會選擇什么時間。按理來說容錯率最高的是8點吧，5點，萬一還沒忙完呢，7點，萬一堵車呢，最遲的時間應該是最好的。你提前到了，那給人印象很好，卡點是正常，遲到就給人不好印象了。這就是最好，折中和最壞預期結果。為了心理預期，我們往往會選擇最遲的點。這樣很好理解了吧

? ? ? ? 在算法中，在一個長度為N數組中搜索一個數據x：

最好情況：1次找到

最壞情況：N次找到

平均情況：N/2次找到

時間復雜度應該是。

4.空間復雜度

? ? ? ? 空間復雜度也是數學表達式，是算法在運行過程中占用內存空間大小的多少，但是說實話真去測算消耗了多少空間？不，算的是變量的個數，也是大O的漸進表示法 O()，依舊舉個例子說明，用斐波那契數列來舉例子：

#include<stdio.h>int Fib(int n)
{if (2>=n){return 1;}else{return Fib(n - 2) + Fib(n - 1);}
}

? ? ? ? 計算有幾個變量，也就是開辟了幾個空間，由于n是不知道的，所以開辟了n個空間，空間復雜度為。

5. 常見的時間復雜度和空間復雜度計算

5.1 時間復雜度計算

? ? ? ? 例1：

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

? ? ? ? 例2：

void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++ k){++count;}for (int k = 0; k < N ; ++ k){++count;}printf("%d\n", count);
}

? ? ? ? 例3：冒泡排序

void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

? ? ? ? 例4：二分查找

int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n-1;while (begin < end){int mid = begin + ((end-begin)>>1);if (a[mid] < x)begin = mid+1;else if (a[mid] > x)end = mid;elsereturn mid;}return -1;
}

? ? ? ? 例5：階乘遞歸

long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

? ? ? ? 例6：斐波那契數列

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

? ? ? ? 案例分析：

案例1，是2N+M，根據大O的漸進表示法，M是個常數，所以是
案例2，是M+N次，根據大O的漸進表示法，M，N都是未知的，所以是
案例3，其實是個冒泡排序，最好的情況就是它是個有序數組，比如{1，2，3，4，5，6.....，n}，那么就只要排n-1次，最壞的情況，就是完全無序，第一趟排，n-1次，第二趟，n-2次，最后一趟，1次。總次數加起來就是（n-1)+(n-2)+(n-3)+.....+1，總和為,所以按最壞的打算時間復雜度O(N^2)
案例4，是個二分查找，最好1次，最壞O(logN)次，時間復雜度為 O(logN) ，logN在算法分析中表示是底數為2，對數為N。ps：二分查找的原理就是縮小一半查找，理想中很好很厲害，但現實中不可靠，因為只適用于有序數組。
階乘算法，最好是1次，最壞是N次，時間復雜度為O(N)。
斐波那契數列，操作了2^N次，所以時間復雜度為O(2^N)。圖解如下：

?

????????不畫圖是很難看出來的，1生2，2生4，4生8，每一個誕生2個函數要執行，所以說畫圖很重要，不畫圖心里是很難憑空心算的。實踐出真知

5.2 空間復雜度計算

? ? ? ? 例1：冒泡排序

void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

? ? ? ? 例2：階乘遞歸

long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}

????????例3 :斐波那契數列

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

案例分析：

例1冒泡排序函數內部，看看開辟了幾個變量，數變量就好了，end，exchange，i，三個，是常數，所以空間復雜度為O(1);
例2遞歸調用了N次，開辟了N個棧幀，每個棧幀又會開辟另一個空間，而遞歸不結束，空間不歸還，所以產生了FAC(N),FAC(N-1),FAC(N-2)........FAC(1),FAC(0)。這是個嵌套調用！！！，沒有銷毀掉，所以空間復雜度為O(N)，不要以為單個棧幀空間里的變量只有一個N，沒有別的變量，你要算N個空間里的變量數量。
例3是1分為2，然后2里面的兩個遞歸用的同一塊空間，是先調用n，然后調用n-1，一直調用到末尾2，符合if條件，返回了！注意開始歸了！2的上一層是3，3下面的2已經調用了，所以會調用另一邊1，1調用了，再返回3。然后發現3的1和2都計算過了，往上返回到4，依次往上，因為遞歸的過程是先遞后歸，遞一邊，遞完返回再歸另外一邊，空間復雜度為O（N），這個案例注意調試，我是調試了很多次，看了很多次N的變化，畫了遞歸流程圖，才看明白,其實講的再多，不如自己去好好的認真調試一遍，就很nice。

?

階乘遞歸空間復雜度

6.時間復雜度對比圖

? ? ? ? 這是我從網絡上找的兩張關于時間復雜度隨著個數的增大的對比圖，（logn理想狀態是很好的）其實時間復雜度要比空間復雜度復雜很多，空間復雜度大多都是O(1),O(N),而時間復雜度會多很多，大家也可以網上找找，大部分圖都是一樣的。

時間復雜度

?????????再者就是常見的時間復雜度參數了

7.結語

????????本篇文章作為數據結構的開篇，就先講這么多，時間復雜度和空間復雜度是貫穿整個數據結構的，另外后面的內容順序表，鏈表等都涉及到動態開辟空間，所以C語言中的動態內存管理以及函數棧幀空間的學習是很必要的，因為順序表，和棧都和通訊錄的撰寫邏輯有關聯。記住一開始說的三點，畫圖，調試，?了解函數棧幀空間?It is imperative?for you?to learn！共同進步，就像gitee里說的，希望你的代碼有朝一日能夠像下面那張圖片一樣。