時間復雜度與空間復雜度分析

raise_yang 發布于2019-08-19 11:33 / 1531人閱讀

摘要：作為開發人員，我們都希望在完成功能的基礎上讓代碼運行的更快更省空間，那如何衡量編寫的代碼是否更有效率，這就需要我們學會如何分析代碼時間復雜度和空間復雜度什么是復雜度分析執行時間和占用空間是代碼性能的個評判標準，我們分別用時間復雜度和空間復雜

作為開發人員，我們都希望在完成功能的基礎上讓代碼運行的更快、更省空間，那如何衡量編寫的代碼是否更有效率，這就需要我們學會如何分析代碼時間復雜度和空間復雜度．

什么是復雜度分析

執行時間和占用空間是代碼性能的２個評判標準，我們分別用時間復雜度和空間復雜度去描述這２個標準，二者統稱復雜度，復雜度描述的是算法執行時間（或占用空間）隨數據規模的增長關系．

為什么需要復雜度分析

有人可能想問我代碼運行一下不就知道他執行多長時間了嗎，為什么還需要復雜度分析，確實你能夠通過這種方法評估出代碼的執行效率，但是這樣會有一些局限性．

1.測試結果太過于依賴測試環境
同一段代碼在不同處理器的機器上運行結果是顯然不一樣的，這時就不知道應該參考哪個測試結果．
2.測試結果受到數據規模的影響很大
兩段不同的代碼在數據量比較小的時候可能相差甚微，無法真實反映代碼的性能問題．

所以我們需要一個不依賴測試環境同時也不需要有具體的測試數據就能粗略的估計代碼的執行效率的方法，也就是復雜度分析．

如何進行復雜度分析

大O復雜度表示法
先看一段代碼，求1,2,3...n的累加和

int calc(int n) {
  int sum = 0;　　//第一行
  for(int i = 1; i <=n; i++) {
    sum = sum + i;
  }
  return sum;
}

我們來評估一下這段代碼的執行時間，假設每行執行的時間一樣，為row_time．第1行需要一個row_time的執行時間，第2，3行分別執行了n次，所以需要2n＊row_time的執行時間，所以這段代碼加起來總共的執行時間為(2n+1)＊row_time，雖然我們并不知道row_time的具體時間，但我們發現代碼的總執行時間T(n)與代碼的執行次數ｎ成正比．我們可以用公式來表示

T(n) = O(f(n))

T(n)代表代碼的總執行時間，f(n)代表代碼的執行次數，O代表T(n)與f(n)成正比．所以上面的例子中，T(n) = O(2n+1)，我們可以看出大O時間復雜度表示代碼執行時間隨數據規模的變化趨勢，我們簡稱為時間復雜度．

當n很大時，公式中的常量，系數都可以忽略不計，并不會對變化趨勢有太大影響，我們只需記下一個最大量級即可，那么剛剛的例子最后就可以記為T(n) = O(n)

那以后的代碼如何去分析其時間復雜度呢，我們有以下法則：
1.看代碼執行次數最多的一段，比如循環
2.多段代碼取最大量級，比如單循環和多重循環，應取多重循環的復雜度
3.嵌套代碼復雜度等于嵌套內外代碼復雜度的乘積，比如遞歸和多重循環等

平時我們有一些常用的復雜度級別，比如O(1) (常數階)、O(logn) (對數階)、O(n) (線性階)、O(nlogn) (線性對數階)、O(n2) (平方階)

了解了時間復雜度，那么空間復雜度也不難理解了，時間復雜度表示的是算法執行時間隨數據規模增長的變化關系，那空間復雜度則表示的是算法存儲空間隨數據規模增長的變化關系．

總結

復雜度用來分析算法執行效率與數據規模增長的變化關系，越高階復雜度的的算法執行效率也就越低，上面列舉的復雜度級別從低到高分別為O(1)、O(logn)、O(n)、O(nlogn)、O(n2)．

GPU云服務器云服務器時間復雜度快速排序時間復雜度最大流算法時間復雜度數據結構時間復雜度

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77453.html

十分鐘弄懂：數據結構與算法之美 - 時間和空間復雜度

摘要：什么是復雜度分析數據結構和算法解決是如何讓計算機更快時間更省空間的解決問題。分別用時間復雜度和空間復雜度兩個概念來描述性能問題，二者統稱為復雜度。復雜度描述的是算法執行時間或占用空間與數據規模的增長關系。這就是大時間復雜度表示法。 showImg(https://segmentfault.com/img/bVbtpFP?w=1000&h=574); 復雜度分析是整個算法學習的精髓，只要...

Salamander 2019-08-23 17:54 評論0 收藏0
【javascript系列】時間復雜度和空間復雜度

摘要：第三段，時間復雜度。五空間復雜度分析空間復雜度的話和時間復雜度類似推算。一、前言時間復雜度和空間復雜度，我們在大學里的算法與數據結構課程中已經學習過，這回根據項目工作中整理一下，這個估計只是一個粗略的估計分析，并不是一個準確的估計分析。 1、學習時間復雜度和空間復雜度是很有必要的，這個屬于算法與數據結構的范疇，學這個是為了解決代碼中的快和省的問題。這樣才能使你的代碼運行效率更高，占...

dcr309duan 2019-08-26 10:18 評論0 收藏0
卷積神經網絡的復雜度分析

摘要：同樣以里的模塊為例，替換前后的卷積分支復雜度如下中使用與卷積級聯替代卷積中提出了卷積的，在確保感受野不變的前提下進一步簡化。在梳理CNN經典模型的過程中，我理解到其實經典模型演進中的很多創新點都與改善模型計算復雜度緊密相關，因此今天就讓我們對卷積神經網絡的復雜度分析簡單總結一下下。1.時間復雜度1.2 卷積神經網絡整體的時間復雜度示例：用 Numpy 手動簡單實現二維卷積假設 Stride...

tracy 2019-04-25 18:21 評論0 收藏0
排序之八大絕技

摘要：需要注意的是排升序要建大堆，排降序建小堆。應用場景需要前個最大或最小元素時，或者與其他排序一塊使用五冒泡排序排序思想大的元素向下沉，小的元素向上浮。目錄一.插入排序 1.插入排序思想 2.動態圖形演示 ?3.插排思路與圖解 4.插入排序代碼實現（升序） 5.時間復雜度，空間復雜度及穩定...

Vixb 2021-11-23 09:51 評論0 收藏0
JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0