数据结构:复杂度分析以及数据结构整体概览
? 復雜度無非是空間，時間復雜度。 掌握了時間，空間復雜度的分析，基本算掌握了數(shù)據(jù)結構與算法的一半內(nèi)容。
? ?之所以引入這幾個復雜度概念，是因為，同一段代碼，在不同輸入的情況下，復雜度量級有可能是不一樣的。
? 分析一段代碼的時間，空間復雜度時候，最需要關注的是循環(huán)次數(shù)最多的代碼。
? ?時間復雜度的全稱是漸進時間復雜度，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關系。
? ?類比一下，空間復雜度全稱就是漸進空間復雜度（asymptotic space complexity），表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關系。
?
如何分析一段代碼的時間復雜度？
?1.? 只關注循環(huán)執(zhí)行次數(shù)最多的一段代碼
?2. 加法法則，總復雜度等于量級最大的那段代碼的復雜度。
?3. 乘法法則，嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積。
?
對于上面羅列的復雜度量級，我們可以粗略地分為兩類，多項式量級和非多項式量級。其中，非多項式量級只有兩個：和。
我們把時間復雜度為非多項式量級的算法問題叫作 NP（Non-Deterministic Polynomial，非確定多項式）問題。
首先你必須明確一個概念，O(1) 只是常量級時間復雜度的一種表示方法，并不是指只執(zhí)行了一行代碼。比如這段代碼，即便有 3 行，它的時間復雜度也是 O(1），而不是 O(3)。
? ? 我稍微總結一下，只要代碼的執(zhí)行時間不隨 n 的增大而增長，這樣代碼的時間復雜度我們都記作 O(1)。或者說，一般情況下，只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬行的代碼，其時間復雜度也是Ο(1)。
? ? ?
2.?O(logn)、O(nlogn)
? ??對數(shù)階時間復雜度非常常見，同時也是最難分析的一種時間復雜度。我通過一個例子來說明一下。
? ?
實際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對數(shù)階的時間復雜度都記為 O(logn)。為什么呢？
我們知道，對數(shù)之間是可以互相轉(zhuǎn)換的，
下面開始進行互換，首先設 a 為 2 將所有數(shù)換為以 2 為底的。將含有 n 的分母移出來。再使用換底公式將?log_23log2?3?換為以 3 為底的。又因為分母的?log_33=1log3?3=1?所以我們換底就成功拉。
參考：?https://blackyau.cc/24.html#ologn-onlogn
如果理解了上面講的 O(logn)，那 O(nlogn) 就很容易理解了。O(nlogn) 也是一種非常常見的算法時間復雜度。比如，歸并排序、快速排序的時間復雜度都是 O(nlogn)。
?
如何分析空間復雜度
? ? ? ?我們常見的空間復雜度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 這樣的對數(shù)階復雜度平時都用不到。而且，空間復雜度分析比時間復雜度分析要簡單很多。所以，對于空間復雜度，掌握剛我說的這些內(nèi)容已經(jīng)足夠了。
?
? ? ? ?1.最好情況時間復雜度（best case time complexity）：在最理想的情況下，執(zhí)行這段代碼的時間復雜度。
? ? ? ?2.最壞情況時間復雜度（worst case time complexity）：在最糟糕的情況下，執(zhí)行這段代碼的時間復雜度。
? ? ? ?3.平均情況時間復雜度（average case time complexity）
? ? ? ? ??最好情況時間復雜度和最壞情況時間復雜度對應的都是極端情況下的代碼復雜度，發(fā)生的概率其實并不大。為了更好地表示平均情況下的復雜度，我們需要引入另一個概念：平均情況時間復雜度。
? ? 4.均攤時間復雜度（amortized time complexity）
?
? ?因為，要查找的變量 x 可能出現(xiàn)在數(shù)組的任意位置。如果數(shù)組中第一個元素正好是要查找的變量 x，那就不需要繼續(xù)遍歷剩下的 n-1 個數(shù)據(jù)了，那時間復雜度就是 O(1)。但如果數(shù)組中不存在變量 x，那我們就需要把整個數(shù)組都遍歷一遍，時間復雜度就成了 O(n)。
? ? ? ?所以，不同的情況下，這段代碼的時間復雜度是不一樣的。
?? ? ?為了表示代碼在不同情況下的不同時間復雜度，我們需要引入三個概念：最好情況時間復雜度、最壞情況時間復雜度和平均情況時間復雜度。
?
?
?
?
數(shù)據(jù)結構整體概覽
?
?
?
總結
以上是生活随笔為你收集整理的数据结构:复杂度分析以及数据结构整体概览的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 期货知识
- 下一篇： 【Linux】目录文件权限的查看和修改【