ランタイムをO（n）に減らす

Question

私はHWのためにこの質問を受け取りました。それを行う方法を理解できません：
配列A [1 ... n]は0からnまでのすべての整数を1つ。配列はソートされません。
この問題では、1回の操作でAの整数全体にアクセスすることはできません。
Aの要素はバイナリで表現されており、それらにアクセスするために使用できる唯一の操作は「一定の時間を要する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であるものとの2つのセットに分割します。小さいセットは、欠落しているビットが持つビットを示します。

小さなパーティションでも同じことをします。

O（n）+ O（n/2）+ O（n/4）...ですので、O（n）は基本的にO（2n）です。一般的な場合について

EDIT

、the following document, bottom of page 1を指します。

基本的には、nが2の累乗でない場合、指定されたnがビット1のパーティションに該当するビット数を正確に知っていることと、 = 0パーティションが完全なセットだった場合。