這個字符串操作代碼的空間複雜度是多少？

這段代碼來自Cracking the Coding面試書。這個字符串操作代碼的空間複雜度是多少？

public static boolean isUniqueChars2(String str) { 
    boolean[] char_set = new boolean[256]; 
    for (int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i); 
     if (char_set[val]) return false; 
     char_set[val] = true; 
    } 
    return true; 
}

而筆者提到，

時間複雜度爲O（n），其中n是字符串的長度，並空間複雜度爲O（n）。

我理解的時間複雜度爲O（N），但我不明白怎麼會空間複雜度爲O（n）的

我的想法： char_set仍將大小爲256的數組無論什麼輸入（str）大小是。即使「str」的長度爲100,000，char_set仍然是一個256個元素的數組。所以我認爲，因爲這個函數的內存要求不會隨着輸入的大小而改變，並且保持恆定的256，所以空間複雜度是恆定的，即O（1）。

有人可以解釋，如果我錯了（並且，爲什麼？）

太謝謝你了。

來源

2013-02-20 anakkala

我認爲你是對的，但是那個作者說那個原始的自我誇張的O（n）（或者你正在通過價值獲得一個副本？）。 – qPCR4vir 2013-02-20 23:26:29

嗯......多數民衆贊成在有趣的。我認爲，當推導漸近複雜性時，我們通常忽略輸入讀取的方式/位置/時間？只關注方法內部發生的事情（考慮到輸入的大小，即n） – anakkala 2013-02-20 23:32:56

我想看看作者的推理。算法本身使用的空間是恆定的。當我們分析空間複雜性時，我們談論的是處理所需的額外*空間量，忽略了算法的輸入。 – 2013-02-21 00:15:50

這是一個比較複雜一點，我想：

迭代的最大數量的一些字符會遇到前兩次是字母串被建立在大小。如果這個大小是有限的，則時間複雜度是O（1），如果不是，布爾數組不能是有限大小，因此空間複雜度將是O（n）。

來源

2013-03-13 22:00:11 collapsar

這個字符串操作代碼的空間複雜度是多少？

回答

相關問題