Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、CliffordSteinによる「 IntroductiontoAlgorithms」という本を読んでいます。「アルゴリズムの分析」の第2章では、次のように述べられています。
また、データの各ワードのサイズにも制限があると想定しています。たとえば、サイズnの入力を処理する場合、通常、整数は定数c>=1のclgnビットで表されると想定します。各単語がnの値を保持できるように、c> = 1が必要です。これにより、個々の入力要素にインデックスを付けることができます。また、単語サイズが任意に大きくならないように、cを定数に制限します。（単語サイズの場合任意に成長する可能性があり、大量のデータを1つの単語に保存し、すべてを一定時間で操作することができます。これは明らかに非現実的なシナリオです。）
私の質問は、各整数がc lg nビットで表される必要があるというこの仮定と、c> = 1の場合、個々の入力要素にインデックスを付けることができる理由です。
まず、lg明らかに対数基数2を意味するためlg n、のビット数も同様nです。
それから彼らが言っているのは、彼らが数字のリストをとるアルゴリズムを持っている場合（私は理解しやすくするために私の例ではより具体的です）、彼らは次のよう1,2,3,...nに仮定しているということです：
メモリ内の「単語」は、これらの数字のいずれかを保持するのに十分な大きさです。
メモリ内の「単語」は、すべての数値を保持するのに十分な大きさではありません（1つの単語に、何らかの形で詰め込まれています）。
アルゴリズムの「ステップ」数を計算する場合、1つの「ワード」に対する操作は1ステップかかります。
彼らがこれを行っている理由は、特定の例（32ビット整数など）を選択せずに、分析を現実的に保つためです（「ネイティブ」タイプでは、ある程度のサイズまでの数値のみを格納できます。その後、任意精度のライブラリに切り替える必要があります）。場合によっては不適切であるか、古くなっている可能性があります。
サイズnの整数を表すには、少なくともlg nビットが必要です。これは、サイズnの入力を格納するために必要なビット数の下限です。定数c>=1に設定すると、下限になります。定数乗数が1未満の場合、nを格納するのに十分なビットがありません。
これは、RAMモデルの単純化されたステップです。これにより、個々の入力値を、メモリの単一のスロット（または「ワード」）でアクセス可能であるかのように扱うことができます。そうでない場合に発生する可能性のある複雑さを心配する必要はありません。（さまざまな単語の長さを許可するモデルを使用した場合、さまざまな単語サイズの値の読み込み、保存、およびコピーにかかる時間は異なります。）これは、「個々の入力要素にインデックスを付けることができる」という意味です。問題の各入力要素は、単一のアドレスまたはインデックス（メモリの1ワードに収まるという意味）でアクセス可能であると想定されているため、モデルが単純化されます。
この質問は非常に昔に行われ、説明は本当に役に立ちましたが、lgnがどのように発生したかについてはまだもう少し明確になる可能性があると思います。私にとって物事を通して話すことは本当に助けになります：
27のように基数10の乱数を選択しましょう。これを格納するには、5ビットが必要です。なんで？27はバイナリで11011だからです。11011には5桁の数字があり、「1桁」はビットと呼ばれるものであるため5ビットであることに注意してください。
各ビットをスロットと考えてください。バイナリの場合、これらの各スロットは0または1を保持できます。5ビットで格納できる最大の数はいくつですか。さて、最大数は各スロットを埋めます：11111
11111 = 31 = 2 ^ 5なので、31を格納するには、5ビットが必要で、31は2^5です。
一般的に（そして明確にするために非常に明示的な名前を使用します）：
numToStore = 2 ^ numBitsNeeded
logは指数の数学的な逆数であるため、次のようになります。log（numToStore）= numBitsNeeded
これは整数にならない可能性が高いため、ceilを使用して回答を切り上げます。したがって、この例を適用して、数値31を格納するために必要なビット数を見つけます。
log（31）= 4.954196310386876=5ビット