---

【數據結構篇】算法征途：穿越時間復雜度與空間復雜度的迷霧森林

💬歡迎交流：在學習過程中如果你有任何疑問或想法，歡迎在評論區留言，我們可以共同探討學習的內容。你的支持是我持續創作的動力！
👍點贊、收藏與推薦：如果你覺得這篇文章對你有所幫助，請不要忘記點贊、收藏，并分享給更多的小伙伴！你們的鼓勵是我不斷進步的源泉！
🚀推廣給更多人：如果你認為這篇文章對你有幫助，歡迎分享給更多對機器學習感興趣的朋友，讓我們一起進步，共同提升！

一、 什么是算法

程序 = 數據結構 + 算法

1. 算法的定義

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作。

此外，算法還有五個重要的特征
1. 有窮性
2. 確定性
3. 可行性
4. 輸入
5. 輸出

接下來我們分別來看這五個特性

1.1 算法的五個特征

1. 有窮性
一個算法必須在有窮步之后結束，且每一步都可在有窮時間內完成。
這里需要注意的是 算法必須是有窮的，而程序可以是無窮的。
2. 確定性
算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出。
3. 可行性
算法中描述的操作都可以通過已經實現的基本運算執行有限次來實現。
4. 輸入
一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合
5. 輸出
一個算法有一個或多個輸入，這些輸出是與輸入有著某種特定關系的量

1.2 好算法的特質

1. 正確性
算法應該可以正確地解決求解的問題
2. 可讀性
算法應具有良好的可讀性，以幫助人們可以理解
3. 健壯性
輸入非法數據時，算法能適當地做出反應或進行處理，而不會產生莫名奇妙的輸出結果
4. 高效率與低存儲量要求
高效率代表花費的時間少 時間復雜度低
低存儲量需求是不費內存 空間復雜度低

• 總結：
  

2. 時間復雜度

可以事先預估時間開銷T(n) 與問題規模n 的關系 (T 表示“time”)
這里我們用一串代碼來看下

#include <stdio.h>// 遞增形love you!
void loveyou(int n){ // n 為問題規模int i = 1;while(i <= n){printf("love you %d\n", i);i++;}printf("I love you too!\n");
}int main(){loveyou(500);return 0;
}

上述代碼結果：

這里我們問題規模是 500 所以我們的:是T(500) = 1 + 501 + 2*500 + 1

如果把500換成n的話 那么
表達式：T(n) = 3n + 3

但是如果表達式多了怎么辦呢 那么
T₁(n) = 3n + 3
T₂(n) = n²+3n + 1000
T₃(n) = n³+ n² + 9999999

若 n = 3000 ，則 ：

3n = 9000 比 T₁(n) = 3n + 3 =9003
n²=9,000,000 比T₂(n) = n²+3n + 1000 = 9,010,000
n³=27,000,000,000 比 T₃(n) = n³+ n² + 9999999 = 27,018,999,999

這時我們可以發現 我們可以只考慮階數高的部分 可以簡化下：
T₁(n) = O(n)
T₂(n) = O(n²)
T₃(n) = O(n³)

算法的復雜度：
最壞時間復雜度： 最壞情況下算法的時間復雜度
平均時間復雜度：所有輸入示例等概率出現的情況下，算法的期望運行時間

• 總結
  

3. 空間復雜度

#include <stdio.h>// 遞增形love you!
void loveyou(int n){ // n 為問題規模int i = 1;while(i <= n){printf("love you %d\n", i);i++;}printf("I love you too!\n");
}int main(){loveyou(500);return 0;
}

解釋： 當我們編輯好這段代碼是 其實需要占多少空間 是已經固定的 這片空間的大小 其實是跟我們問題規模沒有關系的
我們在調用這段代碼時 其實會傳入一個int型的參數
然后我們還定義了一個int型的變量i(int i = 1)
這里需要注意的是 int n (這里的n指的是問題規模）但是不管n的值怎么變化 這個算法執行中 都是一個固定不變的常數值。
無論問題規模怎么變，算法運行所需的內存空間都是固定的常量。
所以這里的算法的空間復雜度為
常數階：S(n) = O(1)

• 注 S表示的是"Space"

并且還需要注意的是 如果是常數階的話 那么我們就可以稱這種算法可以原地工作
我們來看一段簡單的示例代碼：

void test(int n){int flag[0];//聲明長度為n的數組int i;//.....此處省略很多代碼

我們經過上一個例子可以看出 和問題規模是沒有關系的 那么這里我們假設int型變量占的是4個字節(4B)
則所需內存空間 = 4+ 4n + 4 = 4n + 8
那我們就可以寫成 S(n) = O(4n + 8) 他的階數為n 那么
空間復雜度其實是 S(n) = O(n)

我們其實可以看出 如果在函數當中我們定義了某種變量，但是這個變量所占的空間和問題規模n沒有關系的話 這個類型的變量 最多也就是在我們的表達式當中 給我們增添一個常數項 但我們最終要轉換成大O表示法 也就是關心階數的 所以這種常數項 對我們最終結果不會產生任何結果
因此：我們只需要關注存儲空間的大小與問題規模相關的變量就可以了

---

你好，我是意疏。我們一起進步。

意氣風發，漫卷疏狂
學習是成長的階梯，每一次`的積累都將成為未來的助力。我希望通過持續的學習，不斷汲取新知識，來改變自己的命運，并將成長的過程記錄在我的博客中。

如果我的博客能給您帶來啟發，如果您喜歡我的博客內容，請不吝點贊、評論和收藏，也歡迎您關注我的博客。
您的支持是我前行的動力。聽說點贊會增加自己的運氣，希望您每一天都能充滿活力！
愿您每一天都快樂，也歡迎您常來我的博客。我叫意疏，希望我們一起成長，共同進步。

我是意疏 下次見！