Java - 變量的空間複雜度

這裏的空間複雜度是否爲O（n）？因爲如果k增加5，我的變量p也會增加5.Java - 變量的空間複雜度

所有這種方法現在所做的就是讓節點在k處。例如：1-> 5-> 3，當k = 2時，該節點是5

public ListNode reverseKGroup(ListNode head, int k) { 
    int p = 1; 

    while (p < k) { 
     if (head.next == null) { 
      return head; 
     } 
     head = head.next; 
     p++; 
    } 

    return head 
}

來源

2017-07-19 Theo

嚴格考慮你的算法，它具有空間複雜度O（1）。你的輸入是一個列表頭和一個數字k，但是你的算法不會消耗任何空間，而不僅僅是參考head和數字p。在我看來，現有的列表不屬於你的方法的複雜性。但是，你的時間複雜度是O（N）。

---答案西奧在評論的問題：

p是一個數字（在這種情況下，原始的int類型的，所以它需要4個字節 - 大小不變）。如果p增加，這並不意味着，它需要更多的空間，但存儲更高的數字。 p = 5意味着設置了以下字節：「0,0,0,5」，對於p = 257，字節設置爲「0,0,1,2」。我認爲，JVM以big endian字節順序存儲日期，因此第一個零代表較大的字節。隨着小端，字節順序將被顛倒。

當然，你是對的，對於非常大的N，32位長整數是不夠的。因此，嚴格考慮這個事實，需要O（log（N））位來存儲數字，最大爲N。例如數字2^186需要存儲187位（一個1和186個零）。

但實際上，在處理「通常」數據時，您不會期待如此巨大的數量。由於只有超過32位寄存器（一個int數字），您將需要有2^32個數據條目（1條目= 4個字節用於下一個參考，至少4個字節用於參考值Object，並且對象大小本身=至少8個字節），即2^35個字節= 32個千兆字節。因此，當使用數字時，通常認爲它是恆定的空間複雜度。這取決於任務和情況。

來源

2017-07-19 23:22:19 fairtrax

我瞭解時間複雜度部分。對於空間複雜性，我知道使用頭部不佔用任何空間。但是，你能解釋一下如何使用數字p不佔用空間嗎？因爲如果我增加k，不會增加相同的數量，因此我的算法需要空間輸入k，這是O（n）空間複雜 – Theo

@Theo - 我的答案有點長，請參閱編輯的文章。 – fairtrax

非常感謝！ – Theo

根據是否考慮您的空間複雜度的預先存在的結構部分，所述空間複雜度是O（ 1）或O（N），其中N是正在操作的列表的長度，因爲您不添加任何新節點並且僅引用現有節點。

k只對時間複雜性很重要。

來源

2017-07-19 23:15:04 nameless

該算法使用的唯一空間是int p的空間，無論輸入如何，空間複雜度都是O（1）。時間複雜度確實是O（N）。

來源

2017-07-19 23:23:59 NickL

Java - 變量的空間複雜度

回答

相關問題