私は現在、Introduction to Algorithmsの本を読んでいますが、アルゴリズムの分析に関して質問があります。
本によると、マージソートの計算コストは c lg n であり、それは次のように述べています
ワード サイズが任意に大きくならないように、c を定数に制限します (ワード サイズが任意に大きくなる可能性がある場合、1 つのワードに膨大な量のデータを格納し、そのすべてを一定時間で操作できます)。
ここでの「定数」の意味がわかりません。誰かがこれが何を意味するのかを明確に説明できますか?
アルゴリズムの研究における計算の複雑さは、アルゴリズムが必要とする時間 (またはスペース) の上限と下限を提供する関数を見つけることを扱います。高校で線の一般的な点と勾配の公式について学んだ基礎代数を思い出してください。この式 はy = mx + b、m (勾配) と b (y 切片) の 2 つのパラメーターを提供し、直線を完全に記述します。これらの定数 (m,b) は線がどこにあるかを表し、傾きが大きいほど線が急勾配であることを意味します。
アルゴリズムの複雑さは、アルゴリズムの実行にかかる時間 (および/または必要なスペース) の上限 (場合によっては下限) を説明する方法にすぎません。big-O (および big-Theta) 表記を使用すると、アルゴリズム コストの上限 (および下限) を提供する関数を見つけることができます。定数は曲線をシフトするだけで、曲線の形状は変更しません。
ワード サイズが任意に大きくならないように、c を定数に制限します (ワード サイズが任意に大きくなる可能性がある場合、1 つのワードに膨大な量のデータを格納し、そのすべてを一定時間で操作できます)。
物理コンピューターでは、機械語に最大サイズがあります。32 ビット システムでは 32 ビットになり、64 ビット システムではおそらく 64 ビットになります。機械語の操作は、同時に多くのビットを操作する場合でも、(通常) O(1) の時間がかかると想定されます。たとえば、機械語でビットごとの OR またはビットごとの AND を使用する場合、単一時間単位で 32 または 64 の並列 OR または AND 操作を実行すると考えることができます。
コンピューティング システムの理論モデルを構築しようとする場合、機械語の最大サイズの上限を想定する必要があります。これを行わない場合は、「時間 O(1) で n 値の OR を計算する」または「時間 O(1) で 2 つの任意精度数を加算する」などの操作を実行できると主張できます。実際のコンピュータでは実際にはできないことです。したがって、通常、マシン語にはある程度の最大サイズがあるという前提があります。そのため、n 値の OR を計算したい場合でも計算できますが、すべての値を 1 つのマシンにまとめて瞬時に実行することはできません。単語を取得し、単一のアセンブリ命令を実行して結果を取得します。
お役に立てれば！