실행 시간을 O (n)으로 줄이십시오.

Question

나는 HW에 대해이 질문을 가지고 있는데 어떻게해야할지 모르겠다.
배열 A [1 ... n]은 0을 제외하고 0부터 n까지의 모든 정수를 포함한다 . 배열이 정렬되지 않았습니다.
이 문제에서 우리는 한 번의 작업으로 A의 전체 정수에 액세스 할 수 없습니다.
A의 요소는 2 진수로 표시되며, 액세스하는 데 사용할 수있는 유일한 작업은 "일정한 시간이 걸리는 A [i]의 j 번째 비트를 가져 오는 것"입니다.

O (n) 시간에 누락 된 정수를 찾아야합니다.

일반적으로 수행하는 데 걸리는 시간은 O (NlgN) 입니다. N 배열에서 실행하고 N - lgn 비트의 기능인 모든 비트를 가져옵니다.

모든 비트를 읽지 않고 어떻게 할 수 있습니까?

Answer 1

일부 k에 대해 n은 2^k - 1이라고 가정합시다.

하는의는 또한 예제를 보자 여기서 K = 3

000 
001 
010 
011 
100 
101 
110 
111 

당신은 위의 그림과, 각 열 (각 숫자의 장소) 같은 풀 세트가있을 때 동일한 가지고 있음을 알 수 있습니다 1과 0의 수. 물론, 편의상 우리는이를 정렬 된 것으로 보여주고 있지만, 실제로는 그것이 아니라고 말하고 있습니다.

은의 다음 목록 우리는 모든 요소 (O (N))의 첫 번째 비트 살펴

000 
001 
010 
011 
100 
110 
111 

를 살펴보고 다른보다 작은 수를 알아 보자.

첫 번째 비트에는 최상위 비트가 누락 된 1이있는 숫자가 있습니다. 이것은 우리의 숫자가 최상위 비트에 1을 가짐을 의미합니다.

기본적으로 가장 중요한 비트가 1 인 위치와 가장 중요한 비트가 0 인 위치의 두 세트로 분할합니다. 더 작은 세트는 누락 된 숫자의 비트 수를 보여줍니다.

작은 파티션에서도 똑같은 작업을 수행합니다.

O (n) + O (n/2) + O (n/4) ... 기본적으로 O (n) 인 O (2n)입니다.

일반적인 경우 편집

, the following document, bottom of page 1 참조.

기본적으로, n이 2의 거듭 제곱이 아닐 때, 주어진 n, 정확히 얼마나 많은 비트가 비트 1 파티션에 속해야하는지, 비트 = 0 파티션이 완전한 세트이면.