刷題前必學！時間複雜度和空間複雜度！用JavaScript學數據結構與算法詳情 - javascript,算法,數據結構,數據結構和算法,程序員 HowieCong 動態日志

🧑‍💻JavaScript算法與數據結構-HowieCong

務必要熟悉JavaScript使用再來學！

一、時間複雜度

（1）下面代碼，一共執行了幾次？

function traverse(arr){
    // 最沒有懸念的是函數裏面的第一行代碼，只會被執行1次
    var len = arr.length
    // 1. i的初始化語句，只有一次，只會被執行1次
    // 2. i < len，在所有for循環裏面，判斷語句都會比遞增語句多執行一次，所以這裏的判斷語句執行次數就是n+1
    // 3. i++，跟着整個循環體，毫無疑問會被執行n次
    for(var i = 0; i < len; i++){
        // for循環了n次，所以這條語句就被執行n次
        console.log(arr[i])
    }
}

總次數T(n) = 1+n+1+(n+1)+n = 3n+3

（2）規模為n*n的二維數組的遍歷，一共需要執行多少次代碼；

function traverse(arr){
    // 只會被執行1次
    var outLen = arr.length
    // 1. i的初始化，執行一次
    // 2. i < outLen，執行n+1次
    // 3. i++,執行n次
    for(var i = 0; i < outLen; i++){
        //循環n次，執行n次
        var inLen = arr[i].length
        
        // 1. j初始化，執行n次
        // 2. j < inLen，執行n(n+1)次
        // 3. j++，執行n*n次
        for(var j = 0; j < inLen; j++){
            // 因為是兩層循環，所以這貨會被執行n*n = n^2
            console.log(arr[i][j])
        }
    }
}

總次數T(n)= 1+1+(n+1)+n+n+n+n(n+1)+n*n+n^2 = 3n^2+5n+3
（3）代碼執行次數，可以反映出代碼的執行時間，但是如果每次都逐行計算T(n)，事件會變得非常麻煩；算法的時間複雜度，它反映的不是算法的邏輯代碼到底被執行了多少次，而是隨着輸入規模的擴大，算法對應的執行總次數的一個變化趨勢。要想反映趨勢，直接抓住主要矛盾，可以對T(n)做處理
- 若T(n)是常數，那麼簡化為1
- 若T(n)是多項式，比如3n^2+5n+3，我們只保留次數最高那一項，並且將常數係數無腦改為1
- T(n) = 10 => O(n) = 1
- T(n) = 3n^2 + 5n + 3 => O(n) = n^2
（4）思路仍然是計算T(n) => 推導O(n)，實際操作中，O(n)基本可以目測，比如上面的兩個遍歷函數，遍歷N維數組，需要N層循環，只需要關心其最內層那個循環體被執行多少次就可以了
- 規模為n的一維數組，最內層的循環會執行n次，其對應的時間複雜度為O(n)
- 規模為nn的二維數組遍歷時，最內層的循環會執行nn次，其對應的時間複雜度為O(n^2)
- 以此類推，規模為nm的二維數組，最內層的循環會被執行nm次，其對應的時間複雜度就是O(nm)；規模為nn*n的三維數組最內層循環會執行n^3次，因此對應的空間複雜度為O(n^3)

function traverse1(arr){
    var len = arr.length
    for(var i = 0; i < len; i++){
        console.log(arr[i])
    }
}

function traverse2(arr){
    var outLen = arr.length
    for(var i = 0; i < outLen; i++){
        var inLen = arr[i].length
        for(var j = 0; j < inLen; j++){
            console.log(arr[i][j])
        }
    }
}

（5）常見的時間複雜度表達，除了多項式以外，還有logn
- 這個算法讀取一個一維數組作為入參，然後對其中的元素進行跳躍式的輸出。這個跳躍的規則，就是數組下標從1開始，每次會乘以2
```
function fn(arr){
    var len = arr.length

    for(var i = 1; i < len; i = i*2){
        console.log(arr[i])
    }
}
```
- 在有循環的地方，我們關心的永遠是最內層的循環體，這個算法，我們關心console.log(arr[i])到底被執行多少次，也就是知道i\<n(len === n)這個條件是在i遞增多少次後才不成立的
- 假設 i 在以 i = i*2的規則遞增了x次之後，i\<n開始不成立（反過來説也就是 i >= n成立）。此時我們計算的就是 2^x >= n;x解出來，就是大於等於以2為底數為n的對數：x >= log2n
- 只有當x小於log2n的時候，循環才是成立的、循環體才能執行，涉及到對數的時間複雜度，底數和係數都是要被簡化掉的，那麼這裏O(n) = logn
（6）常見的時間複雜度按照從小到大的順序排列

二、空間複雜度

空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度。時間複雜度相似，它是內存增長的趨勢。常見的空間複雜度有O(1)、O(n)和O(n^2)

理解空間複雜度，如下例子:

function traverse(arr){
    var len = arr.length
    for(var i = 0; i < len; i++){
        console.log(arr[i])
    }
}

在函數traverse，佔用空間有以下變量
- arr,len,i
這裏的arr，並不是一個不變的數組，arr最終大小是由輸入的n的大小決定的，會隨着n的增大而增大，呈現一個線性關係，因此這個算法的空間複雜度就是O(n)
假如需要初始化的是一個規模為n*n的數組，那麼它的空間複雜度就是O(n^2)

❓其他

1. 疑問與作者HowieCong聲明

如有疑問、出錯的知識，請及時點擊下方鏈接添加作者HowieCong的其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
若想讓作者更新哪些方面的技術文章或補充更多知識在這篇文章，請及時點擊下方鏈接添加里面其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
聲明：作者HowieCong目前只是一個前端開發小菜鳥，寫文章的初衷只是全面提高自身能力和見識；如果對此篇文章喜歡或能幫助到你，麻煩給作者HowieCong點個關注/給這篇文章點個贊/收藏這篇文章/在評論區留下你的想法吧，歡迎大家來交流！