第二節(jié) 基本概念

要點(diǎn)

  • 時(shí)間復(fù)雜度
  • 空間復(fù)雜度

1.1 時(shí)間復(fù)雜度

  • 代碼的執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù) n 成正比。
  • 大O表示法只關(guān)注n的最高階；也就是說：分析一個(gè)算法、一段代碼的時(shí)間復(fù)雜度的時(shí)候，也只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了

計(jì)算規(guī)則

    1. 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
    1. 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
      如果 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)))
    1. 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
      ``
      如果 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))

  • 最好情況時(shí)間復(fù)雜度：在最理想的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度

  • 最壞情況時(shí)間復(fù)雜度：在最糟糕的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度

  • 平均情況時(shí)間復(fù)雜度：

  • 加權(quán)平均時(shí)間復(fù)雜度

  • 均攤時(shí)間復(fù)雜度

``

1.2 空間復(fù)雜度

空間復(fù)雜度(Space Complexity)是對一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲空間大小的量度。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 樹的定義 之前一直介紹的是一對一的線性結(jié)構(gòu)，可現(xiàn)實(shí)中還有多一對多的情況需要處理，這就是今天要介紹的一對多的數(shù)據(jù)結(jié)構(gòu)...
    JsCoderr閱讀 1,830評論 0贊 3
  • 超級賬本是Linux基金會(huì)發(fā)起的項(xiàng)目，意在提供一套企業(yè)級區(qū)塊鏈應(yīng)用框架，便于大家開發(fā)基于區(qū)塊鏈技術(shù)的應(yīng)用。 Fab...
    Abububiu閱讀 1,767評論 0贊 0
  • 一、數(shù)據(jù)結(jié)構(gòu) 1.基本概念 1.1數(shù)據(jù) 程序的操作對象,用于描述客觀事物. 1.2.數(shù)據(jù)的特點(diǎn) 可以輸入到計(jì)算機(jī) ...
    MrDemon_閱讀 347評論 0贊 0
  • 算法： 解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令標(biāo)識一個(gè)或多個(gè)操作。 算法的特性：...
    暮想sun閱讀 104評論 0贊 0
  • 一、什么是算法 1.1 算法和程序的區(qū)別 算法的定義：計(jì)算或解決問題的步驟和思想?？梢詫⑺惴ū扔髯鍪匙V，想要做出特...
    無憂_c063閱讀 291評論 0贊 0

友情鏈接更多精彩內(nèi)容