空間複雜度：鏈接列表節點數組（頭）

給定單個鏈表的頭節點數組，數組的空間複雜度是多少？我會得出結論，假設每個節點只包含一個指向下一個的指針，空間複雜度將是o（n）。但是，當我console.log /打印單個節點時，會顯示整個列表。有可能空間複雜度爲o（n * m），其中m是數組中每個鏈表的長度？這裏是一個小例子：空間複雜度：鏈接列表節點數組（頭）

// JavaScript (ES6) 

class Node { 
    constructor(value) { 
    this.value = value 
    this.next = null 
    } 

    const A = new Node('a') 
    const B = new Node('b') 
    const C = new Node('c') 
    const D = new Node('d') 

    A.next = B 
    B.next = C 
    C.next = D 

    console.log(a)

這是的console.log的結果：

{ 
    value: "a", 
    next: { 
     value: "b", 
     next: { 
      value: "c", 
      next: { 
       value: "d", 
       next: null 
      } 
     } 
    } 
}

因此，當放置在Node A陣列：[A]，將空間複雜度的上升或保持恆定？

來源

2017-02-27 Loschtreality

空間複雜度爲O(n)。

你從console.log()看到的是它在打印時追逐了幾層指針，因爲這些數據在調試時往往是非常有用的。但是如果你自己通過鍵/值，你會發現它有一個固定的大小。

來源

2017-02-27 22:55:35 btilly

空間複雜度：鏈接列表節點數組（頭）

回答

相關問題