我在做面試準備時遇到了這個問題。public class Main { public static void main(String[] args) { // n is some user input value int i = 0; while (i < n) { int[] a = new int[n]; for (int j = 0; j < n; j++){ a[j] = i * j; } i++; } }}給出的選擇是：上）O(n^2)據我所知，答案應該是 O(n)，因為在每次迭代中都會創建一個新的數組實例，并且會丟失先前的引用。然而，書中提到的答案是 O(n^2)?？赡艿慕忉屖鞘裁矗?
2 回答
慕標琳琳
TA貢獻1830條經驗 獲得超9個贊
解釋
你的解釋是正確的?？臻g復雜度是線性的。
但是，您的結論（以及本書作者的結論）是錯誤的。正確答案是兩個答案都正確。也就是說，空間復雜度是：
O(n)和O(n^2)
Big-O 給出了一個上限，而不是確切的界限。想想它<=而不是 just =。因此，如果a in O(n)它也是真的a in O(n^2)（從數學上講，Big-O 給出了一組函數）。
精確界限由Theta ( =) 給出，下界由Omega ( >=) 給出，嚴格下界由small-omega ( >) 給出，嚴格上限由small-o ( <) 給出。所以空間復雜度在Theta(n).
有關詳細信息和實際數學定義，請參閱維基百科。
筆記
如果我們假設 Java 的垃圾收集器處于活動狀態，則空間復雜度僅為線性?？梢越盟蛴脤嶋H上不釋放內存的模擬實現替換它（請參閱Epsilon-GC）。
在那種情況下，空間復雜度確實是二次的。
算法本身需要分配二次方的內存。但是，它只會同時持有線性數量的內存?？臻g復雜度分析通常是根據必須同時保留多少內存來完成的。但也許作者想分析算法總共需要分配多少，這也可以解釋他的選擇。
aluckdog
TA貢獻1847條經驗 獲得超7個贊
這本書似乎完全錯了。執行所需的空間是 O(n)。至于可能的解釋：作者考慮到了運行時的復雜性。嵌套循環給出了 O(n^2) 運行時復雜度。如果這本書比較新且流行，它可能有一個勘誤表網頁，這可能會闡明它。
添加回答
舉報
0/150
提交
取消