은 O (d) 시간 이진 표현 (D 숫자 포함) 매우 큰 소수를 변환 할 수 있는가?는 이진 표현은 10^6 자리 십진수로 변환
여기서 d = log (n). 여기서 d는 십진수의 숫자입니다 (예 : 10^6). 그래서 숫자는 분명히 10^(10^6)보다 적습니다.
O (d)또는 O (d C) 단계를 수행하는 알고리즘이있는 경우. 공유하십시오. 여기서 d은 10 진수의 자릿수입니다.
O (d)에 대한 응답이 없습니다.
증명 (엄격하지 않음)
10 진수 x(k)가 k 번째 자리 (최하위 숫자로 시작하는)이다 x(k)*10^k의 k 위에 합으로 작성 될 수있다.
10은 2와 5의 두 요소로 구성됩니다. 2는 간단한 비트 시프트이지만 5는 2 비트 집합입니다. 이 결과는 k 자릿수를 더할 때 고쳐야하는 비트 수는 상수에 의해 제한되지 않는다는 것입니다. 임의의 정수인 경우, 1*10^k의 0이 아닌 비트의 수가 m보다 커야하므로 k이 있습니다.
따라서 한 자리 당 필요한 작업량 (최대)은 일정하지 않으며 k이 올라갑니다.
올바르게 읽으면 대답은 아니오입니다. 여기서 n은 자릿수 인 O (log n)에서 10 진수를 2 진수 표현으로 변환 할 수 없습니다. 모든 숫자를 스캔해야하므로 시간 복잡도는 적어도 O (n)입니다. 올바르게 읽지 못하면 질문을 수정해야합니다. –
언어는 자릿수로 시간을 조정하는 것과 거의 관련이 없습니다. – Evert
10^6 자리의 숫자에 대한 이진 표현을 찾으려고합니다. 누구든지 그렇게 할 수있는 최적의 방법을 제안 할 수 있습니까? –