O (n) 대신 O (1)의 공간 복잡성을 어떻게 만들 수 있습니까?

Question

반복 프로세스를 사용하여 소수를 2 진수로 변환하려고합니다. O (n) 대신 O (1)의 공간 복잡성을 어떻게 만들 수 있습니까? 값 자체가 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 비트를위한 장소가 필요하지 않습니다. 너는 log2(n)+1이 필요하다. n 비트를 사용하면 잘못된 결과가 나오지 않지만 큰 값인 n 인 경우 Java 프로세스에서 사용할 수있는 메모리가 충분하지 않을 수 있습니다.

그리고 약 O(1) ... 당신은 생각했다 아마 정말 무엇을 :하지만,
Javas int은 (양) int 값이 최대 31 비트를 필요로하는 보장에 이르게 특정 고정 된 값의 범위를 (있는 경우가 음수도 있습니다. 기호를 어딘가에 저장해야합니다. 32 비트입니다.).

엄밀히 말하면 정확히 정확히 31 번 반복되도록 루프를 다시 작성하면 O (1)을 얻을 수 있습니다. 그런 다음 각 값이 n 인 경우 코드의 단계 수가 정확히 같고 정의 당 O(1)입니다.

비트 피딩 경로로 이동하면 도움이되지 않습니다. 값이 특정 조건을 충족시키는 경우 유용한 바로 가기가 있지만 int 값으로 코드를 사용하려면 여기에있는 일반 루프를 사용하는 것이 가장 좋습니다.

비트 연산자, 그리고 일반적으로 (또는 "비트가 손보는") 비트 조작에 최대 읽기