|
定数時間（ていすうじかん、）は、計算複雑性理論における用語で、問題の計算にかかる時間が入力として与えられるデータの大きさに依存せず一定であることを指す。O(1) で表される。 例えば、配列のひとつの要素にアクセスするのにかかる時間は、その場所を指定する1つの命令（操作）だけでよいため、一般に定数時間である。しかし、ソートされていない配列から最小の要素を探す問題は定数時間ではなく、検索にそれなりの時間を要する。アルゴリズム（選択アルゴリズム）を工夫しない場合、その処理には線形時間すなわち O(n) の時間を要する。要素数が既知で変化しないなら、アルゴリズムによっては定数時間となるものもある。 == 関連項目 == *ランダウの記号 *多項式時間 *線形時間 *指数関数時間 en:Time complexity#Constant time 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「定数時間」の詳細全文を読む スポンサード リンク
|