今天開始數據結構的學習！作為一大重點，拿出態度很重要，想要真實掌握，博客筆記自然少不了！重點全部上色！避免疏忽

下面我們從0基礎開始學習今天的第一節！不用擔心看不懂，拒絕枯燥的理論概念！? ?

目錄

對“算法”的理解

“算法復雜度”概念理解

? ? ? ??一? 時間復雜度的表示與計算

? ? ? ? ? ? ? ? ? ? ? ?一.1? 時間復雜度實例講解

? ? ? ? ? ? ??一.2? “約會”預期管理類時間復雜度

? ? ? ? ? ? ??一.3? “約會”預期管理類時間復雜度實例講解

? ? ? ? ? ? ??一.4? 時間復雜度的意義

二? 空間復雜度的表示與計算?

? ? ? ? ? ?? ?二.1? 空間復雜度實例講解

---

對“算法”的理解

算法簡而言之，就是解決問題的步驟跟指令，通過一系列操作，從而達到預期的結果

“算法復雜度”概念理解

哈是算法復雜度？

概念：度量算法性能優劣的一個量級說明

度量算法主要從兩個方面來考慮：時間復雜度? ? 空間復雜度

時間復雜度作用：體現執行這個算法所需要的計算工作量（下面是完整概念）

比如：對2個算法進行比較，若算法A較算法B更加快，此時指它的時間復雜度更好?

空間復雜度作用：體現執行這個算法所需要占用的額外的內存空間大小（下面是完整概念）

下面我們分別來進行講解！?

一? 時間復雜度的表示與計算

表示：首先它的表示用大O符號表示（O（n）），這個n（下面參考例題詳解！）表示這個問題的? ? ? ? ? ? ?一個工序規模次數?，O（n）也叫大O表示法

計算規則：

? ? ? ? ? ? ? ? ??1：用常數1來取代運行時間中所有加法常數

? ? ? ? ? ? ? ? ? 2：只要高階項，不要低階項

? ? ? ? ? ? ? ? ? 3：不要高階項系數

常見的時間復雜度（復雜度由低到高）：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（1）? ? ? ? ? ? ?常數階

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（n）? ? ? ? ? ? ?線性階

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（n^2）? ? ? ? ?平方階

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（logn）? ? ? ? 對數階

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（nlogn）? ? ? nlogn階

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（n^3）? ? ? ? ?立方階

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（2^n）? ? ? ? ?指數階

畫圖演示：

一.1? 時間復雜度實例講解

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??實例1

第一步：我們計算出這個工程的工序次數是 2*N+10?次

第二步：根據計算規則進行刪除

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 只要高階項，不要低階項，去除10，首先得到：2*N

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 不要高階項系數，去除2，最后得到：N

第三步：得出最終結果，Func2的時間復雜度為 O（N）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??實例2

第一步：計算這個工程的執行工序，得到：M+N? 次

第二步：根據計算規則進行刪除更改：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?因為M與N都是未知數，因為最高階階數相同，也無常數? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?故全部保留

第三步：得出時間復雜度：O（M+N）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 實例3? ? ??

第一步：計算這個工程的總工序，得到100? 次

第二步：根據計算規則進行更改與刪除：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?用常數1取代所有加法常數，100改為1，最終得到1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?注：這個“1”代表常數次，不是代表1次?

第三步：得到時間復雜度：O（1）

一.2? “約會”預期管理類時間復雜度

難道跟“約會”有關嗎？沒錯沒錯！下面如果是你和你的對象約會，你會選擇哪個時間點？? ? ? ? ? ? ?? ?最早：下午17：00

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 大概：下午19:00

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??最遲：下午20:00

我們來分析一下，因為這只是一個引入，所以無法符合每個人的想法啊！

如果我們把對每件事的期望盡量拉小，那么當這件事不管完沒完成，對你的打擊也就越小！

如果失敗：那么我的期望也沒那么高，管的他呢！

如果成功：帶給我的期望是不是更多一些！

下面我們針對非直接性（需要分情況考慮）的對時間復雜度的計算：

另外一些時間復雜度存在幾種考慮情況：比如計算：什么時候可以從一堆字符串找到一個對應字符

有以下幾種情況：

? ? ? ? ? ? ? ? ? ? ? ? ? ? 直接一次找到，這屬于最好情況（下界）

? ? ? ? ? ? ? ? ? ? ? ? ? ? 找到末尾才找到，這屬于最壞情況（上界）

? ? ? ? ? ? ? ? ? ? ? ? ? ? 最壞與最好平均下來，就是平均情況

那么我們假設一個長為N的字符串，對應幾種情況分別是：1次

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?N次

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?N/2次

在實際情況中一般關注的是算法的最壞運行情況，所以數組中搜索數據時間復雜度為O（N），取最壞情況

一.3? “約會”預期管理類時間復雜度實例講解

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?實例1

第一步：得到這個問題的最壞工序次數為 7 次

第二步：根據計算規則進行刪除與更改：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?用常數1取代所有加法常數，7改為1

第三步：得到Srchr的時間復雜度為 O（1）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? 實例2

第一步：計算這個問題的最壞情況下執行次數，為N^2（也就是N的平方）

第二步：根據計算規則進行刪除與更改：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 與三條規則不沖突，不用更改

第三步：得到它的時間復雜度為 O（N^2）

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 實例3

二分查找涉及數學邏輯，下面配有演示！

?第一步：計算這個問題最壞情況工序為 logN（也就是log以2為底的N的對數）

第二步：根據計算規則刪除與更改：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?與三條規則不沖突，直接保留

第三步：得出時間復雜度為 O（logN）

我們看數學演示計算過程：假設N是數組個數，x表示最壞查找數

查詢次數	記錄
1	N/2
2	N/2/2
3	N/2/2/2
x	N/2^x

我們發現：每查詢一次，就需要除一次2

? ? ? ? ? ? ? ? ? 那么查詢x次，就表示N/2^x

? ? ? ? ? ? ? ? ? 有2^x=N（注意：查一次有一個2，那么查了x次，就是2^x，數組有N個元素，那么最? ? ? ? ? ? ? ? ? ? ? 壞情況就是N=2^x）

? ? ? ? ? ? ? ? ? 那么最壞查找數? x=log2N

由于：log以2為底的N的對數不好寫這個底數，所以規定：凡是以2為底的對數可以直接寫為logN

注：只適用于以2為底的對數 可以寫為? logN（底數2可以不寫）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?實例4

（斐波那契數的計算，下圖配有數學解析）?

?第一步：計算這個問題的最壞工序次數：

第二步： 根據計算規則進行刪除與更改：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 去除高階項系數2^（N-1）=2^N * 2^（-1），最終得2^N

第三步：得到時間復雜度 O（2^N

一.4? 時間復雜度的意義

學會時間復雜度的計算，可以更理解題目的要求，以及比較平時代碼的性能，比如：

我們可以看到上面有時間復雜度的限制，那么我們在寫題目時，需要先大概計算一下時間復雜度！?

二? 空間復雜度的表示與計算

空間復雜度我們之前已經大概了解了一下：? ?運行算法過程中額外占用存儲空間大小的量度

表示：與時間復雜度類似，還是用大O表示法：O（n），其中n表示變量個數，n一般等于變量個數+額外開辟次數（不是字節數）

計算：依然遵循時間復雜度的三條原則

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

下面我們來進行例題操練！

二.1? 空間復雜度實例講解

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 實例1

第一步：計算圖中的變量個數以及看是否額外占用空間

? ? ? ? ? ? ? ?發現創建了3個變量，并沒有額外開創空間（帶?i?的循環是在n里面的，所以?i?用的是n開? ? ? ? ? ? ? ? ?辟的那個空間，沒有重新開辟）

第二步：按照三條規則重新刪除與更改：常數項改為1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（3）也就變成了O（1）

第三步：得出空間復雜度為O（1）

? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?實例2

第一步：分析變量個數與額外開辟空間大小 （變量個數+額外開辟空間）

第二步：計算?額外占用存儲空間大小為O（n+1+1）

? ? ? ? ? ? ? 按照三個規則進行刪除與更改：只要高階項，不要低階項，改為O（n）?

第三步：得出空間復雜度 O（n）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??實例3

第一步：計算變量個數以及額外占用的空間?

每次調用函數都需要開辟空間，一共調用了N+1次 （這個空間的開辟是計算開辟次數，不是字節）

?第二步：根據三條規則進行刪除與更改：不要地階項，只保留高階項

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O（N+1）更變為 O（N）

第三步：空間復雜度為 O（N）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

以上就是? ?算法復雜度? 的全部講解了！寫的好的話記得一鍵三連哦！希望每天都是陽光明媚！