教練.jpeg

為什么想學?

• 如果你是一名業(yè)務開發(fā)工程師番宁，你可能要說元莫，我整天就是做數據庫CRUD（增刪改查）又或者你像我一樣是個前端仔，整日最常用的命令就是npm run dev蝶押，哪里用得到數據結構和算法磅獯馈？那還有必要學習復雜度分析嗎棋电？
• 是的朽基，對于大部分開發(fā)來說，網上的現有框架已經足夠我們平時的開發(fā)了,很多現成的框架离陶，封裝使用方便，拿來就用衅檀，還不用太擔心性能的問題招刨。而我們已經很少需要自己實現數據結構和算法。
• 不需要自己實現哀军，并不代表什么都不需要了解沉眶。如果不知道這些類庫背后的原理，不懂得時間杉适、空間復雜度分析谎倔，你如何能用好、用對它們猿推？調用了某個函數之后片习，你又該如何評估代碼的性能和資源的消耗呢？而數據結構和算法學習的精髓就是復雜度分析

為什么需要復雜度分析蹬叭？

• 之前的我通過代碼跑一遍藕咏，通過統(tǒng)計、監(jiān)控秽五，就能得到算法執(zhí)行的時間和占用的內存大小孽查。為什么還要做時間、空間復雜度分析呢坦喘？
  1. 測試結果依賴測試環(huán)境
     測試環(huán)境中硬件的不同會對測試結果有很大的影響盲再。比如西设，用不同的cpu處理器 i9處理器上的代碼顯然會比i3處理器上的代碼運行的快。
  2. 測試結果受數據規(guī)模的影響很大答朋。比如測試數據規(guī)模太小贷揽，測試結果可能無法真實地反應算法的性能。
• 我們需要一個不用具體的測試數據來測試绿映，就可以粗略地估計算法的執(zhí)行效率的方法擒滑。這就是時間、空間復雜度分析方法叉弦。

大O復雜度表示法

算法的執(zhí)行效率丐一，其實就是算法代碼執(zhí)行的時間。如何在不運行代碼的情況下淹冰，來評估一段代碼的執(zhí)行時間呢库车？

1. 求1,2,3…n的累加和，那么段這代碼的執(zhí)行時間又是多少呢樱拴。

   var Sum = function(n) {
       let result = 0
       for(let i= 0;i<n;i++){
           result = result+i
       }
       return result
   };
   

   可以看到每一行的代碼都執(zhí)行著類似的操作：讀取-運算-記錄柠衍。在這里粗略估計，就可以假設每行代碼執(zhí)行的時間都一樣晶乔，為n_time珍坊。

   第2行代碼需要1個為n_time的執(zhí)行時間，第3,4行都運行了n遍正罢，所以需要2nn_time的執(zhí)行時間阵漏，所以這段代碼總的執(zhí)行時間就是(2n+1)n_time。

2. var Sum = function(n) {
           let result = 0
           for(let i= 0;i<n;i++){
                for(let j= 1;j<n;j++){
                   result = result+i*j
                }
           }
           return result
       };
   

   我們依舊假設每個語句的執(zhí)行時間是n_time翻具。那這段代碼的總執(zhí)行時間T(n)是多少呢履怯？
   第2行代碼，每行都需要1個n_time的執(zhí)行時間裆泳，第3行代碼循環(huán)執(zhí)行了n遍叹洲，需要n * n_time的執(zhí)行時間，第4工禾、5行代碼循環(huán)執(zhí)行了n2遍运提，所以需
   要2n2 * n_time的執(zhí)行時間。所以闻葵，整段代碼總的執(zhí)行時間T(n) = (2n2+n+1)*n_time糙捺。

   通過這兩段代碼執(zhí)行時間的推導過程，我們可以得到一個非常重要的規(guī)律笙隙，那就是洪灯，所有代碼的執(zhí)行時間T(n)與每行代碼的執(zhí)行次數n成正比。
   我們可以把這個規(guī)律總結成一個公式。

   T(n)=Of(n)
   T(n)表示代碼執(zhí)行的時間签钩；n表示數據規(guī)模大刑秃簟；f(n)表示每行代碼執(zhí)行的次數總和;O表示代碼的執(zhí)行時間T(n)與f(n)表達式成正比铅檩。

   第一個例子中的T(n) = O(2n+1)憎夷，第二個例子中的T(n) = O(2n2+n+1)。這就是大O時間復雜度表示法昧旨。大O時間復雜度實際上并不具體表示代碼真正的執(zhí)行時間拾给，而是表示代碼執(zhí)行時間隨數據規(guī)模增長的變化趨勢，所以兔沃，也叫作漸進時間復雜度（asymptotic time complexity）蒋得，簡稱時間復雜度。

   當n很大,甚至趨近于∞時乒疏。在公式中的低階额衙、常量、系數三部分并不能影響他的趨勢怕吴，所以都可以忽略窍侧。我們只需要記錄一個最大量級就可以，如果用大O表示法表示剛講的那兩段代碼的時間復雜度转绷，就可以記為：T(n) = O(n)伟件； T(n) = O(n2)。

時間復雜度分析

1. 只關注循環(huán)執(zhí)行次數最多的一段代碼最多法則

   大O這種復雜度表示方法表示一種變化趨勢议经。所以锋爪，我
   們在分析一個算法、一段代碼的時間復雜度的時候爸业，也和大O這種復雜度一樣只關注循環(huán)執(zhí)行次數最多的那一段代碼就可以了。這段核心代碼執(zhí)行次數的n的量級亏镰，就是整段要分析代碼的時間復雜度扯旷。

   還是上文的代碼，這次我們來分析他的時間復雜度

   var Sum = function(n) {
       let result = 0
       for(let i= 0;i<n;i++){
           result = result+i
       }
       return result
   };
   

   其中第2行代碼是常量級的執(zhí)行時間索抓，只是聲明了一個變量與n的大小無關钧忽，所以對于復雜度并沒有影響。循環(huán)執(zhí)行次數最多的是第3逼肯、4行代碼耸黑，這兩行代碼被執(zhí)行了n次，所以總的時間復雜度就是O(n)篮幢。

2. 總復雜度等于循環(huán)次數最多的那段復雜度大刊。加法法則

   var Sum = function(n) {
       let sum1 = 0
       for(let i = 0;i<1000;i++){
           sum1 = sum1+i
       }
       let sum2 = 0
       for(let j= 0;j<n;j++){
           sum2 = sum2+j
       }
       let sum3 = 0
       for(let k= 1;k<n;k++){
           for(let m = 0;m<n;m++){
               sum3 = sum3+k*m
           }
       }
       return sum1+sum2+sum3
   }
   

   這個代碼分為三部分，分別是求sum1三椿、sum2缺菌、sum3葫辐。可以分別分析每一部分的時間復雜度伴郁，然后取一個量級最大的作為整段代碼的復雜度耿战。

   第一段的時間復雜度是多少呢？這段代碼循環(huán)執(zhí)行了1000次焊傅，所以是一個常量的執(zhí)行時間剂陡，跟n的規(guī)模無關。因此無論這個這段代碼循環(huán)了多少次只要是一個已知的數與n無關那么當n趨向∞時就可以忽略狐胎。因為它本身對算法執(zhí)行效率與數據規(guī)模增長的趨勢并沒有影響鸭栖。

   第二段，第三段代碼的時間復雜度分別是O(n)和O(n2)綜合這三段代碼的時間復雜度顽爹，取其中最大的值纤泵。整段代碼的時間復雜度就為O(n2)。

   抽象成公式T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))

3. 遇到嵌套的 for 循環(huán)的時镜粤，時間復雜度呢就是內外循環(huán)的乘積捏题。乘法法則

```
var Sum = function(n) {
    let result = 0
    let func =  function(n) {
        let func_result = 0
        for(let j= 1;j<n;j++){
            func_result = func_result +j
        }
        return func_result
   }
    for(let i = 1;i<n;i++){
        result = result+func(i)
    }
    return result
} 
```
如果func()函數只是一個普通的操作，那第10～12行的時間復雜度就是肉渴，T1(n) = O(n)公荧。但func()函數本身不是一個簡單的操作，而其本身的時間復雜度是T2(n) =
O(n)同规，所以循狰，整個Sum()函數的時間復雜度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)券勺。

抽象成公式 **T(n)=T1(n)??T2(n)=O(f(n)? g(n))** 

幾種常見時間復雜度分析

對于復雜度量級可以分為以下兩類多項式量級和非多項式量級

• 多項式量級

  1. O(1)
     通常被稱為常量階绪钥，他時間復雜度的一種表示方法，并不是指只執(zhí)行了一行代碼关炼。即便有多行程腹，它的時間復雜度也是O(1),一般情況下，只要算法中不存在循環(huán)語句儒拂、遞歸語句寸潦，即使有成千上萬行的代碼，其時間復雜度也是Ο(1)社痛。
  2. ** O(n)** 線性階
  3. ** O(n2)...O(n?)** 線性階
  4. ** O(logn)见转、O(nlogn)**
     對數階,線性對數階時間復雜度非常常見，例如

     var Sum = function(n) {
         let i=1
         while (i <= n) {
             i = i * 2;
         }
         return i
     }
     

  根據我們前面講的復雜度分析方法蒜哀，第4行代碼是循環(huán)執(zhí)行次數最多的斩箫。所以，我們只要算出這行代碼被執(zhí)行了多少次，就能知道整段代碼的時間復雜度校焦。
  變量i的值從1開始取赊抖，每循環(huán)一次就乘以2。當大于n時寨典，循環(huán)結束氛雪。而i的取值就是一個等比數列

  2? 21 22 23 ...... 2? = n
  

  通過2x=n求解x可以算出x=log2?，所以耸成，這段代碼的時間復雜度就是O(log2?)

  而實際上报亩，不管是以2為底、以3為底井氢，還是以10為底弦追，因為對數之間可以互相轉化，例如log3? = log32 *log2? 所以O(log3?) = O(C * log2?)因為C是個常量我們又可以像在大O復雜度中一樣將它忽略掉因此可以把所有對數階的時間復雜度都記為O(logn)花竞。

  而如果一段代碼的時間復雜度是O(logn)劲件，我們循環(huán)執(zhí)行n遍，時間復雜度就是O(nlogn)了约急。

  3. ** O(n)**

• 非多項式量級

  1. O(2?)和O(n!)零远。指數階，階層階

空間復雜度分析

時間復雜度的全稱是漸進時間復雜度厌蔽，表示算法的執(zhí)行時間與數據規(guī)模之間的增長關系牵辣。相似的，漸進空間復雜度（asymptotic space complexity）簡稱就是空間復雜度表示算法的存儲空間與數據規(guī)模之間的增長關系奴饮。

var Sum = function(n) {
    let result = []
    for(let i= 0;i<n;i++){
        result[i] = i 
    }
    return result
};

跟時間復雜度分析一樣纬向，我們可以看到，第2行代碼中戴卜，我們聲明了存儲變量result逾条，整段代碼的空間復雜度就是O(n)。
我們常見的空間復雜度就是O(1)投剥、O(n)师脂、O(n2)，

image

最好情況時間復雜度薇缅、最壞情況時間復雜度、平均情況時間復雜度

• 是什么攒磨？
  1. 最壞情況時間復雜度：代碼在最理想情況下執(zhí)行的時間復雜度泳桦。
  2. 最好情況時間復雜度：代碼在最壞情況下執(zhí)行的時間復雜度。
  3. 平均時間復雜度：用代碼在所有情況下執(zhí)行的次數的加權平均值表示娩缰。

• 為什么要引入這幾個概念灸撰？
  1. 同一段代碼在不同情況下時間復雜度會出現量級差異，為了更全面，更準確的描述代碼的時間復雜度浮毯。
  2. 代碼復雜度在不同情況下出現量級差別時才需要區(qū)別這幾種復雜度完疫。大多數情況下，是不需要區(qū)別分析它們的债蓝。

寫在最后

image

漸進時間壳鹤，空間復雜度分析為我們提供了一個很好的理論分析的方向，他能夠讓我們對我們的程序或算法有一個大致的認識饰迹，復雜度分析能讓我們對不同的算法有了一個“效率”上的感性認識芳誓。

漸進式時間，空間復雜度分析僅僅只是一個理論模型啊鸭，只能大概的分析锹淌，不能直接斷定就覺得O(logn)的算法一定優(yōu)于O(n)

所以在實際開發(fā)中，時刻關心理論時間赠制，空間度模型是有助于產出效率高的程序的赂摆，同時，而通過文中提供的粗略的分析模型钟些，也不會浪費太多時間烟号，重點在于要具有這種復雜度分析的思維。