定数時間

定数時間（ていすうじかん、英: Constant time）は、計算複雑性理論における用語で、問題の計算にかかる時間が入力として与えられるデータの大きさに依存せず一定であることを指す。O(1) で表される。

例えば、配列のひとつの要素にアクセスするのにかかる時間は、その場所を指定する1つの命令（操作）だけでよいため、一般に定数時間である。しかし、ソートされていない配列から最小の要素を探す問題は定数時間ではなく、検索にそれなりの時間を要する。アルゴリズム（選択アルゴリズム）を工夫しない場合、その処理には線形時間すなわち O(n) の時間を要する。要素数が既知で変化しないなら、アルゴリズムによっては定数時間となるものもある。

関連項目