• 💂 個人主頁: IT學習日記
• 🤟 著作權: 本文由【IT學習日記】原創、在CSDN首發、需要轉載請聯系博主
• 💬 如果文章對你有幫助、歡迎關注、點贊、收藏(一鍵三連)和訂閱專欄哦
• 💅 想尋找共同成長的小伙伴，請點擊【技術圈子】

📔 一、前言

• 大家好，我是小誠，國慶放假后跟一些小伙伴聊天時發現，大家潛意識里都知道想要進入大廠演算法是必須過關的，所以很多人在學校就開始去刷題了，題目雖然刷了許多，但是對于學習演算法的初衷和衡量一個演算法的指標卻是模糊的，所以，博主想寫一篇關于學習演算法的初衷和演算法的指標，幫助準備學習演算法或者初學演算法的小伙伴將基礎鞏固，

• 本篇文章重點介紹：演算法相關知識的介紹，和衡量演算法的指標(時間復雜度和空間復雜度)

• 如果文章對你有幫助，可以幫忙一鍵三連和專欄訂閱哦！

📕 二、專欄推薦

??良心推薦： 下面的相關技術專欄還在免費分享哦，大家可以幫忙點點訂閱哦！

??面試干貨專欄

??JAVA進階知識專欄

??從0到1-全面深刻理解MySQL系列專欄

📗 三、了解演算法

🔴 3.1、學習演算法的必要性

??說明： 必要性就從實際用途方面介紹(至于那些：演算法是進入大廠必備的技能這種原因就跳過了)，

??看過我之前博客的小伙伴應該知道，我在很多博文中都有提到一句話，“一個概念或者技術的出現必然是為了解決存在的某個問題”，那演算法出現的必要性是因為什么呢，在開發者的世界中有一種說法：能夠使用硬體解決的問題就不需要軟體解決，這個說法是否正確?，下面來舉個例子，讓大家有更直觀的感受，

??大家都了解計算機中主要的計算組件就是CPU，假設某個問題可以通過兩種演算法(簡稱為演算法1、演算法2)解決，它們的時間復雜度分為O(n)和O(n2)(時間復雜度不懂的沒關系，后面會介紹)，假設現在某型號CPU的運算速度提升了100倍，我們分別配置稍微低一點的CPU去跑時間復雜度為O(n)的演算法，和使用提升了100倍的CPU去跑時間時間復雜度為O(n2)的演算法，我們會發現一個結果：使用配置低的硬體運行的效率要比配置高的硬體效率更好，這是為什么？

??原因就在于演算法的復雜度，演算法2的復雜度為O(n2)，雖然使用了提升了100倍運算速率的CPU去執行它，但是相對于運行讓它運行復雜度的O(n)的演算法，它提升的速率實際上僅為10倍， 搭配了提升100倍運算速率CPU的計算機就好好比生活中的小車，搭配了硬體配置較低的計算機就好比生活中的單車，如果單車的速度都比小車快(單單考慮速度方面)，你還會考慮購買小車？畢竟小車的價格是單車的幾倍？

??通過上面簡單的例子，我們會發現：硬體的速度提升并不是我們不去考慮開發出更高效率應用的借口，作為一名開發者，至少對自己開發的應用要有所標準！所以，開發一個程式時使用更好性能的演算法是一名合格程式員應該考慮的因素，

🔵 3.2、何為演算法

??上面一小節，我們通過具體的例子解釋了學習演算法的必要性，那么接下來我們就來認識下什么是演算法，

??演算法：

??并不是什么高深的詞匯，可以理解為它就是解決特定問題的辦法，在計算機中表現為有限的指令序列，同一個問題有多種解決辦法，所以某一個問題的演算法并不是唯一的，就好像我們想去旅游，可以乘坐高鐵動車、也可以坐飛機，

??同一個問題，不同的演算法雖然得到的是相同的結果，但是它們耗費的時間和資源是存在差異的，所以在解決特定問題的時候，我們在多種演算法中選出最好的一種， 就好比如果旅游的目的地比較近，可以乘坐高鐵，這樣可以節省花費，如果比較遠，可以考慮乘坐飛機，可以直達，避免中間換乘等時間和金錢的花費，

??那如何才能從多種演算法中選擇最好的最好的一種呢？想要實作這個目的，那我們需要先了解衡量一個演算法好壞的指標是那些，然后再根據這些指標去進行選擇，

🟣 3.4、演算法的特征

??一、何為真正的演算法：

??上一節中提到：演算法就是解決某個或者某類問題的辦法，但是，這只是對演算法的一個籠統的描述，一個真正的演算法，包含以下5大特性：輸入、輸出、有窮性、確定性、可行性，

• 輸入輸出： 演算法具有零個或者多個輸入，至少一個或者多個輸出，輸入可以為零，但是必須存在輸出，輸出的形式可有為確定的回傳值或者日志的的列印等，如果沒有輸出，那演算法的意思在哪里呢？

• 有窮性： 指演算法在執行有限的步驟后可以自動結束，不會出現無限的回圈，且每個步驟在可以接受的時間完成，注意：這里的有窮性并不是單純數學上的概念，它指的是一個可以接收的“邊界”，如存在某種演算法運行幾年后可以得出結果，理論上也是符合有窮性，

• 確定性： 演算法的每一個步驟都是具有確定的意義，不會出現歧義，相同的輸入必須得到相同的輸出，

• 可行性： 演算法中每一步都可以轉換成程式在計算機上運行，它意味著演算法中的設計是可行的，但是并不意味著一定得到正確的結果，

??二、好演算法有哪些評判標準：

??上一節我們介紹了一個演算法具有的哪些特征，但是演算法也分好壞，好的演算法效率高，就好比“移山”，如果在古代可能只能用人力去挖，現代的話可以使用各種炸藥、自動化設備去處理，不僅效率更高，安全性也更好，那么，衡量一個演算法好壞有哪些標準呢？下面具體來看看吧！

??2.1、正確性：

??正確性：要求演算法應該有輸入、輸出和執行無歧義，能夠正確反映問題的具體需求，通過演算法能夠得到解決問題的正確答案，

??2.1.1、“正確性”演算法的四個層次

??（1）演算法程式沒有語法錯誤

??（2）演算法程式對合法的輸入能夠得到滿足要求的輸出

??（3）演算法程式對非法的輸入能夠得到滿足規格的輸出

??（4）演算法程式對故意刁難的測驗資料能夠得到滿足要求的輸出

??對于演算法的第4層次，基本不可能實作將所有的輸入逐一驗證，所以演算法的正確性一般只要滿足到第3層次即可，

??2.2、可讀性：

??一個好的演算法設計，應該是方便大家閱讀、理解和交流的，如果為了追求某些方面的特性，導致演算法不易于人們理解，那這樣的演算法不能稱為好的演算法，因為人們無法輕易讀懂它，導致難以修改和除錯，即使演算法中存在問題也不能輕易發現，最后可能演算法的設計者在時間久遠后也很難理解它，

??2.3、健壯性：

??好的演算法應該對不合理的輸入做到適當的處理(提示等)，而不是產生讓使用者也無法理解的例外或者莫名其妙的結果，

??健壯性定義： 演算法的輸入資料不合法時，演算法能夠做出相應的適當處理，而不是產生難以理解的例外或者莫名其妙的結果，

??2.4、時間效率高和存盤量低：

??演算法也是來源生活，生活中我們都希望花最少的錢辦最多的事，演算法也是一樣，能夠占用最小的空間，最快的得到結果那就是一個好的演算法，

??時間效率高： 指的是通過演算法設計的程式執行的時間短，一個問題存在著多種演算法可以解決，使用時間最短的那個時間效率最高，

??存盤量低： 存盤量是指實作演算法的存盤在運行時占用最大的存盤空間，程式運行占用的空間越小，證明運行程式需求的資源越小，演算法就越好(存盤空間一般是指：記憶體或者硬碟等設備的存盤空間)，

🟡 3.4、演算法和程式的區別

??有些小伙伴可能會將演算法和程式兩者的概念混淆，其實它們兩者是不同的概念，演算法表示的是解決某個或某類問題的思路、想法，程式是根據某一個特定演算法撰寫出來可以被計算機運行的代碼，

??就比如我需要輸出1到100范圍內的所有數值，我們會考慮到使用回圈陳述句輸出，使用回圈陳述句輸出這個思路就可以說是演算法，然后實際上根據這個思路撰寫出來的代碼就可以稱為程式，

📘 四、演算法效率的度量方法

??通過上文的介紹，大家已經對演算法有了初步的了解，但是，實際情況如何衡量一個演算法的好壞呢，相信現在大家心里都還是存在著這個疑惑的，下面就來看看有哪些度量方法吧！

🔶 4.1、事后統計方法

??定義：不同的演算法設計出不同的測驗程式進行測驗，然后統計計算機計時器在不同測驗程式運行的時間進行比較，從而確定演算法效率的高低，

??1.1、事后統計方法存在的問題

??1、某個問題或某類問題可以存在多種演算法解決，如果每種演算法都撰寫測驗程式需要花費大量的時間和精力，

??2、運行效率依賴于計算硬體和軟體等環境因素，不同的硬體和軟體有可能會掩蓋了演算法存在的問題，導致測驗出來的結果不準確，

??3、測驗資料設計準備困難，程式的運行效率往往和測驗資料的規模有關，如果測驗資料太小，以現在CPU的運算速度，根本看不出差異，選擇多大的測驗資料規模，測驗多少次才能夠得到比較準確的結果等，這些問題都是很難進行判斷的，

??1.2、事后統計方法結論

??基于事后統計方式存在的缺陷，這種演算法效率的度量方式是不推薦使用的，

🔷 4.2、事前統計方法

??定義：在進行演算法程式撰寫前，依據統計方法對演算法進行估算，得到演算法程式運行的預估值， 計算機的前輩們經過分析發現，通過高級程式語言撰寫的程式在計算機運行時消耗的時間取決于下面的幾個因素：

??通過上面的圖片可以發現，因素2取決于軟體的支持，因素4取決于運行程式的硬體，拋開軟體、硬體有關的因素，一個程式的運行效率，依賴于演算法的好壞和問題的輸入規模(即輸入量的多少)，

??下面我們通過求和的兩種演算法來實際分析與程式的運行時間相關的具體因素：

??演算法一：累加求和

int i,sum=0,n=100; // 執行1次
for(i=1;i<n;i++){
	sum = sum + i; // 執行n次
}
System.out.println("sum="+sum); // 執行1次

??演算法二：高斯演算法

int i,sum=0,n=100; // 執行1次
sum = (1 + n) * n / 2; // 執行1次
System.out.println("sum="+sum); // 執行1次

??通過上面求和的兩個演算法我們會發現，如果將頭尾變數定義和回圈判斷等開銷忽略，實際上兩種演算法就是運行n次和1次的區別，隨著n的數值越大，它們之間運行的次數差距也越大，程式花費的時間差距也越大，因此，我們可以得出一下的一個結論：

??測定運行時間最可靠的方法，就是計算對運行時間有消耗的基本操作的執行次數，運行時間和這個計數成正比，

??結論：

??對于輸入規模為n，第一種求和演算法中，求和操作 sum = sum+ i 代碼需要被運行n次，我們可以說這個問題的輸入規模n使得程式的運算元量是：f(n) = n

??對于輸入規模為n，第二種演算法中求和代碼：sum = (1 + n) * n / 2 始終只需要執行一次，那么我們可以說這個問題的輸入規模為n使得程式的執行數量是：f(n) = 1

??因此，在進行分析一個演算法的運行時間時，我們需要將輸入規模和程式的基本運算元量進行關聯起來即將基本運算元量表示成輸入規模的函式，如下圖所示：

📙 五、時間復雜度和空間復雜度

🟧 5.1、時間復雜度

??在資料結構中，使用時間復雜度來衡量程式運行時間的多少，每條陳述句執行的次數稱為該陳述句的頻度，整段代碼的總執行次數則稱為整段代碼的頻度，

??定義：在演算法估算時，陳述句的執行次數T(n)是關于問題規模n的函式，從而分析T(n)隨著n的變化的關系，演算法的時間復雜度也稱為演算法的時間量度，記作T(n) = O(f(n))，它表示隨著問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，稱作演算法的漸進時間復雜度，簡稱為時間復雜度，其中f(n)是問題規模n的某個函式，

??剛開始看上面的定義多少有些迷惑，但是多讀幾次結合上文的知識串起來后，你會其實并沒有這么復雜，時間復雜度其實可以理解為隨著問題規模n的增大，程式陳述句執行頻度的增長率，

??在定義中我們使用到O()的方式來體現演算法時間復雜度的記法，這種方式又稱為大O記法，一般情況下，隨著問題規模n的增大，T(n)即陳述句執行次數增長最慢的演算法為最優演算法，講簡單點，就是無論你輸入規模如何變化，只要執行的陳述句次數增長最小，那這種演算法就是最優的，

??了解演算法時間復雜度的定義，那么如何分析一個演算法的時間復雜度呢(即如何推到大O階呢)?沒錯，經過前輩們的經驗，這個也是有相應的推導公式的，在推導的時候我們應該采用無限大的思想來簡化大O運算式，具體如下：

• 用常數1代替運行時間中的所有加法的常數，如：某個演算法的執行函式為f(n) = 10，則替換成大O階方法的話則為：O(1)，無論這個常數為10，還是100，還是1000都使用1替換，因為執行函式和問題規模n的大小無關，它是執行時間恒定的，像時間復雜度為O(1)的又被稱作常數階，

• 如果運算式有多項含有無限大變數的式子，只保留一個擁有指數最高的變數的式子，例如 2n2+2n 簡化為 2n2；

• 如果最高階項存在且系數不為1，則去除掉與這個項相乘的系數，例如 2n2 系數為 2，直接簡化為 n2 ；

??經過上面三個步驟推到出來的結果就是演算法對應的大O階，

??對演算法的時間量度，存在兩種方式， 一種是計算所有情況的平均值，這種時間復雜度的計算方法稱為平均時間復雜度，另一種情況則為計算最壞情況下的時間復雜度，這種也稱為最壞時間復雜度，一般沒有特殊說明的情況下，指的都是最壞時間復雜度，

🟨 5.2、常見的時間復雜度例子

??一、常數階

int i,sum=0,n=100; // 執行1次
sum = (1 + n) * n / 2; // 執行1次
System.out.println("sum="+sum); // 執行1次

??這個演算法就是上面我們舉例到的高斯演算法，程式的執行次數函式為f(n) = 3，根據大O階方法的推導方式，則得到的時間復雜度為：O(1)，而不是O(3)，注意：因為執行函式并不會隨著n的變化而變化，它是恒定的，像復雜度為O(1)，又被稱作常數階，

??二、線性階

int i,sum=0,n=100; // 執行1次
for(i=1;i<n;i++){
	sum = sum + i; // 執行n次
}
System.out.println("sum="+sum); // 執行1次

??根據上面的代碼，我們可以發現執行次數函式為f(n) = n，根據大O階方法的推導方式得到它的時間復雜度表示為：O(n)， 像這種線性階，我們主要分析的是回圈結構中的一個運行情況，從而得到它的時間復雜度，

??三、對數階

int condition = 1;
while(condition < n){
	condition = condition * 2;
}

??根據上面的代碼，我們會發現回圈陳述句的條件會在每次condition乘以2后更加接近跳出條件，既滿足多少個與2的乘積后將會退出回圈，因此我們可以得到執行次數的函式為：f(n) => 2^x = n ===> x = log₂n，根據大O階方法的推導方式得到它的時間復雜度表示O(logn)，

??四、平方階

for(int i=o;i<n;i++){
	for(int j=o;j<n;i++){
		...
	}
}

??根據代碼分析，我們可以得到執行次數的函式為: f(n) = n²，根據大O階方法的推導方式得到它的時間復雜度表示O(n²)，

??五、常見的時間復雜度耗費時間比較

??O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ ) < O(n!) < O(nⁿ)

🟦 5.3、空間復雜度

??在資料結構中，用空間復雜度來衡量程式運行所需記憶體空間的大小，跟時間復雜度類似，它也可以使用大O記法來表示，

??演算法的空間復雜度是通過計算演算法所需的存盤空間實作的，計算公式為：S(n) = O(f(n))，其中n為問題的規模，f(n)則為陳述句關于問題規模n所占存盤空間的函式，隨著n的變動，f(n)的增長率越小越好，

??一個演算法程式從編譯到運行有多個部分涉及存盤空間的分配，具體情況如下：

• 程式代碼本身需要占用一部分存盤空間，用于存盤編譯后提供執行的代碼，這部分的存盤空間主要取決于程式的代碼量，因此，為了減少這部分占用的空間，在保證演算法的合理性情況下，應該盡量減少代碼量，

• 程式中的輸入輸出，也需要占用一部分存盤空間，這部分的占用的空間主要取決于不同演算法的實作邏輯，但是大體上它們的大小都是相差不大的，

• 程式在運行時，不同情況下需要申請的臨時空間，這部分占用的空間是對空間復雜度影響最大的，因為不同的演算法實作細節可能存在較大的差異，會申請的空間也會存在比較大的不同，

??一、常見的空間復雜度可以歸類為以下的幾種情況：

• 如果演算法執行時所需要的空間和演算法的輸入值無關，對于輸入資料量來說是一個常數的話，則稱該演算法為 原地作業 空間復雜度為O(1)，

• 如果隨著輸入資料量 n 的增大，程式申請的臨時空間成線性增長，則程式的空間復雜度用 O(n) 表示，

• 如果隨著輸入資料量 n 的增大，程式申請的臨時空間成 n² 關系增長，則程式的空間復雜度用 O(n2) 表示，

• 如果隨著輸入資料量 n 的增大，程式申請的臨時空間成 n³ 關系增長，則程式的空間復雜度用 O(n3) 表示，

• 等等(和時間復雜度的推送邏輯類似)

??堅持閱讀到此處的小伙伴，恭喜你，在演算法方面已經初步入門了，接下來就是需要多次閱讀，將文章中沒有理解清楚的概念搞清楚，然后再結合具體的演算法(leetcode網站)進行實戰，有了理論知識的支撐，相信你實戰的腳本會更加快捷，

📜 六、參考資料

??《大話資料結構》

??說明： CSDN中，該書籍僅供會員在線閱讀，無法下載，所以博主正在找電子版同步到【技術圈子】中，有需要的小伙伴可以掃描下面二維碼進入【技術圈子】，

🚀 七、寫在最后

??也許大家看完文章后會還是存在些許疑惑，這個是非常正常的，解決辦法就是將不理解的概念整理出來，多看幾遍，你會有不同的領悟，演算法的學習對每一位有自我要求的開發者來說應該都是必須的，如果讀完后還是存在疑惑，歡迎私信博主或者進入【技術圈子】提問，

??推薦一下： 【技術圈子】目的是為了搭建共享資源平臺，因為很多人尋找資源路徑有限，但是人多力量大，將它們整理起來尋找資源的方式就多了，也更容易了，

??博主保證：圈內所有資源都免費，資源包括但不限于免費面試資源、簡歷模板、年侄訓報PPT、CSDN VIP下載資源等等，無論你是大學生、還是已經作業的開發者，都期待您的加入!感興趣者可以掃描下面二維碼或者查看左邊導航欄進入技術圈子，

??如果文章對你有幫助，請幫忙點擊"一鍵三連" 和 “專欄訂閱”，感謝您的支持！期待下一篇文章繼續看到你的身影！