長碼空間複雜度（輔助）

每當我們計算額外空間時，我們都不會將輸入視爲計算的一部分。比方說，我們需要一種算法來打印一個數字，單詞，相當於像1爲「一」，2爲「二」等長碼空間複雜度（輔助）

一個這樣做的方式將每個數字被映射到其詞等同。

Map<Integer, String> map = new HashMap<>(); 
map.put(1, "One"); 
..... 
map.put(Integer.MAX_VALUE, "Something equivalent");

然後有一個函數返回單詞。這將考慮具有O（N）額外的存儲空間。

我的問題是，如果我們寫一個函數這樣

public printDigit(int n) { 
    switch(n) { 
     case 1: 
      return "One"; 
     ... 
     case Integer.MAX_VALUE: 
      return "Something equivalent"; 
    } 
}

通常情況下，我們不考慮代碼空間的使用是額外的空間？我不習慣那種邏輯，因爲我從來沒有遇到過它。所以我們將這個算法稱爲O（1）額外的空間，因爲我們沒有額外的數據結構來存儲;

來源

2016-10-30 Zanko

通常情況下，我們考慮一個算法，適用於所有可能的輸入大小。在這種情況下，算法的大小並不重要，因爲對於非常大的輸入大小它可以忽略不計。 – mcdowella

如果編譯器決定將切換例存儲在跳轉表中，則空間複雜性將不再是O(1)，因爲實現類似於C++中的映射或Java中的哈希映射。相反，它會是O(N)。

編譯器可用的其他選項是對提供的案例進行線性搜索或二分法搜索。在所有這些選項中，必須將每個交換機箱存儲在某種形式的容器中。在所有這些情況下，空間複雜性將會是O(N)。

首先，爲了可讀性，switch-statement比if-else更優選。但是，在代碼中使用map可以提供簡潔和更好的可維護性。

來源

2016-10-30 04:30:41

長碼空間複雜度（輔助）

回答

相關問題