文章目錄
一、事后統計法
二、分析預測法 -- 時間、空間復雜度分析法
大 O 時間復雜度表示法
時間復雜度分析方法
1. 只關注循環執行次數最多的一段代碼；
2. 加法法則：總的時間復雜度等于量級最大的那段代碼的復雜度；
3. 乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積；
4. 幾種常見時間復雜度實例分析
4.1. O(1)
4.2. O(logn)、O(nlogn)
4.3. O(m+n), O(m*n)
5. 最好、最壞、平均和均攤時間復雜度
5.1 最好情況時間復雜度
5.2 最壞情況時間復雜度
5.3 平均情況時間復雜度
5.4 均攤情況時間復雜度
數據結構和算法解決的是快和省的問題，即如何讓代碼運行的更快，如何讓代碼更節省存儲空間。一個非常重要的考量指標是算法的執行效率，分析方法有事后分析和提前預測兩種–事后統計法和時間、空間復雜度分析法。
一、事后統計法
即讓代碼在計算機硬件上實際運行一遍，并監控和統計出算法執行實際花費的時間和占用的內存。這種方法很正確，但是有如下缺點：
測試結果依賴測試的軟硬件環境；
測試結果受數據規模和復雜度的影響很大；
并不能確定運行的算法是否最優。
因此我們需要一種方法，以便在構思和編寫算法時，不用實際運行就可以粗略估算和預測算法的執行效率，這可以指導我們編寫出符合業務要求且效率高的算法程序。
二、分析預測法 – 時間、空間復雜度分析法
大 O 時間復雜度表示法
作為粗略估計，我們可以認為每行代碼執行（讀-運算-寫）所需要的時間都一樣，且假定為單位時間 unit_time。這里有兩種情況：目標代碼不包含循環；目標代碼包含循環。對于前者，很簡單，執行完一次就完了，執行時間是個固定值，這沒什么好研究的；對于后者，由于非循環部分代碼的執行時間是固定的，那么目標代碼總體執行時間取決于循環體代碼的執行時間，這由循環體行數以及各行循環的次數(可能出現嵌套循環)，方便起見總計為循環 n 次，那么總的執行時間就是 n 的函數了，記為 T(n)。很顯然，目標代碼的執行時間 T(n) 與數據規模 n 成正比，記為：
其中：T(n) 表示代碼執行的時間，n 表示數據規模的大小（循環總次數），f(n)表示每行代碼執行的次數總和，O表示正比關系。這就是大 O 時間復雜度表示法。
注意，大 O 時間復雜度實際上并不具體表示代碼真正的執行時間，而是表示代碼執行時間隨數據規模增長的變化趨勢，所以也叫漸近時間復雜度，簡稱時間復雜度。
當 n 很大時，公式 f(n) 中的低階、常量、系數并不左右增長趨勢，可忽略，而只需要關注最大量級的那部分即可。
時間復雜度分析方法
1. 只關注循環執行次數最多的一段代碼；
2. 加法法則：總的時間復雜度等于量級最大的那段代碼的復雜度；
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n))).
3. 乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積；
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).
注意：復雜度分析無需記憶上述公式，只需多看案例多練習分析，就能掌握。
4. 幾種常見時間復雜度實例分析
以上可組略分為兩類：多項式量級和非多項式量級。只有 O(2n) 和 O(n!) 屬于后者。
非多項式量級的時間復雜度算法，隨著數據量的增大，算法執行的時間急劇增加，所以這些算法是非常低效的。
4.1. O(1)
表示算法執行時間為常量的算法。一般情況下，只要算法中不存在循環、遞歸等操作，該算法的時間復雜度就是常量級。
4.2. O(logn)、O(nlogn)
可通過下面案例理解O(logn)：循環體中 i = i * 2; 的執行次數為 log2n次
i=1;
while (i <= n) {
i = i * 2;
}
通過對數的換底公式，其他任意底的對數都可以轉換成常系數形式的log2n（Clog2n），而常系數又是可以忽略的，所以任意對數復雜度的算法可統一將其復雜度表示為logn。
關于O(nlogn)，通過時間復雜度乘法法則可知，O(nlogn) = O(n) * O(logn)，可簡單理解為復雜度為 O(logn) 的代碼被循環執行了 n 遍。常見的歸并排序、快速排序的時間復雜度就是 O(nlogn)。
4.3. O(m+n), O(m*n)
兩個數據規模未知的算法的復雜度有如上表示。
復雜度分析并不難，關鍵在多練習!
5. 最好、最壞、平均和均攤時間復雜度
5.1 最好情況時間復雜度
5.2 最壞情況時間復雜度
5.3 平均情況時間復雜度
運用概率知識算出的期望值（加權平均值）。
說明：很多時候使用一個復雜度就可以滿足需求，只有同一塊代碼塊在不同情況下，時間復雜度有量級的差距時，才會使用最好、最壞和平均來區分。
5.4 均攤情況時間復雜度
一種特殊的平均情況時間復雜度
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
