如何使這個空間複雜度爲O（1）而不是O（n）？

Question

我想使用迭代過程將小數轉換爲二進制數。我怎樣才能讓這個空間複雜度爲O（1）而不是O（n）？

int i = 0; 
int j; 
int bin[] = new int[n]; //n here is my paramater int n 
while(n > 0) { 
    bin[i] = n % 2; 
    n /= 2; 
    i++; 
} 

//I'm reversing the order of index i with variable j to get right order (e.g. 26 has 11010, instead of 01011) 
for(j = i -1; j >= 0; j--) { 
    System.out.print(bin[j]); 
} 

Answer 1

首先，如果值本身是n你不需要的地方n位。您只需要log2(n)+1。它不會給你錯誤的結果來使用n位，但對於大值n，Java進程可用的內存可能不夠。

而且，關於O(1) ...也許不是真的是自己所想的，但：
Java類int具有特定的固定值範圍，這導致了一個（正）int值需要最多31位的保證（如果你也有負數，需要在某處存儲符號，這是32位）。

有了這些信息，嚴格來說，你可以通過重寫你的循環得到O（1），使它們循環31次。然後，對於每個值n，您的代碼具有完全相同的步驟數量，即每個定義爲O(1)。

去點擺弄路線在這裏沒有幫助。如果你的值滿足某些條件，有一些有用的快捷方式，但是如果你想讓你的代碼使用任何int值，那麼你在這裏的正常循環可能是你能得到的最好的循環。

（yourse中，CPU內部函數可以幫助，但不能對Java ...）