これをO（n）ではなくO（1）の空間の複雑さにするにはどうすればよいですか？

Question

私は、反復処理を使用して小数を2進数に変換しようとしています。これをO（n）ではなくO（1）の空間の複雑さにするにはどうすればよいですか？

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) ...あなたが考えていたのかもしれない、本当に何が、：
Javas intは（正）int値は最大31ビットを必要としていることを保証につながる特定の固定値の範囲を、（もし持っていますあなたは負の数も持っています、記号をどこかに格納する必要があります、それはビットです32）。

厳密に言えば、正確に31回ループするようにループを書き直すだけで、O（1）を得ることができます。次に、それぞれの値がnの場合、コードはステップごとに同じ量を持ち、定義ごとにO(1)になります。

ここでは、ビットバイディングルートに行くことは役に立ちません。あなたの値が特定の条件を満たしている場合、いくつかの便利なショートカットがありますが、あなたのコードが任意のint値で動作するようにしたい場合、ここにある通常のループが得られる可能性が最も高いでしょう。一般的には

（yourseのうち、CPUの組み込み関数は助けではなく、Java用も...）