成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

時(shí)間復(fù)雜度與空間復(fù)雜度分析

raise_yang / 1540人閱讀

摘要：作為開發(fā)人員，我們都希望在完成功能的基礎(chǔ)上讓代碼運(yùn)行的更快更省空間，那如何衡量編寫的代碼是否更有效率，這就需要我們學(xué)會(huì)如何分析代碼時(shí)間復(fù)雜度和空間復(fù)雜度什么是復(fù)雜度分析執(zhí)行時(shí)間和占用空間是代碼性能的個(gè)評判標(biāo)準(zhǔn)，我們分別用時(shí)間復(fù)雜度和空間復(fù)雜

作為開發(fā)人員，我們都希望在完成功能的基礎(chǔ)上讓代碼運(yùn)行的更快、更省空間，那如何衡量編寫的代碼是否更有效率，這就需要我們學(xué)會(huì)如何分析代碼時(shí)間復(fù)雜度和空間復(fù)雜度．

什么是復(fù)雜度分析

執(zhí)行時(shí)間和占用空間是代碼性能的２個(gè)評判標(biāo)準(zhǔn)，我們分別用時(shí)間復(fù)雜度和空間復(fù)雜度去描述這２個(gè)標(biāo)準(zhǔn)，二者統(tǒng)稱復(fù)雜度，復(fù)雜度描述的是算法執(zhí)行時(shí)間（或占用空間）隨數(shù)據(jù)規(guī)模的增長關(guān)系．

為什么需要復(fù)雜度分析

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

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

所以我們需要一個(gè)不依賴測試環(huán)境同時(shí)也不需要有具體的測試數(shù)據(jù)就能粗略的估計(jì)代碼的執(zhí)行效率的方法，也就是復(fù)雜度分析．

如何進(jìn)行復(fù)雜度分析

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

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

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

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

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

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

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

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

了解了時(shí)間復(fù)雜度，那么空間復(fù)雜度也不難理解了，時(shí)間復(fù)雜度表示的是算法執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化關(guān)系，那空間復(fù)雜度則表示的是算法存儲(chǔ)空間隨數(shù)據(jù)規(guī)模增長的變化關(guān)系．

總結(jié)

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/77453.html

相關(guān)文章

  • 十分鐘弄懂：數(shù)據(jù)結(jié)構(gòu)與算法之美 - 時(shí)間和空間復(fù)雜度

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

    Salamander 評論0 收藏0

  • 【javascript系列】時(shí)間復(fù)雜度和空間復(fù)雜度

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

    dcr309duan 評論0 收藏0

  • 卷積神經(jīng)網(wǎng)絡(luò)的復(fù)雜度分析

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

    tracy 評論0 收藏0

  • 排序之八大絕技

    摘要：需要注意的是排升序要建大堆，排降序建小堆。應(yīng)用場景需要前個(gè)最大或最小元素時(shí)，或者與其他排序一塊使用五冒泡排序排序思想大的元素向下沉，小的元素向上浮。 目錄 一.插入排序 1.插入排序思想 2.動(dòng)態(tài)圖形演示 ?3.插排思路與圖解 4.插入排序代碼實(shí)現(xiàn)（升序） 5.時(shí)間復(fù)雜度，空間復(fù)雜度及穩(wěn)定...

    Vixb 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、插入排序、選擇排序

    摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...

    canger 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<