상수 시간

계산 복잡도 이론에서 상수 시간(常數時間) 또는 O(1)의 시간이란, 어떤 문제를 풀이하는데 필요한 수학적 연산 시간이 주어진 입력 자료에 관계 없이 일정할 때의 연산 시간을 의미한다.

예를 들어, 배열 또는 메모리에 있는 하나의 원소에 접근하기 위해서는 단 하나의 연산이면 충분한데, 이런 경우에 배열 또는 메모리에 접근하는 데 걸리는 계산 복잡도를 상수 시간이라고 한다. 그러나 정렬되지 않은 배열 내의 최소 값을 찾아내기 위해서는 각 원소를 조회해야 하므로 이에 걸리는 계산 시간은 상수 시간이 아니며 (이진 검색과 같은 더 효율적인 알고리즘을 사용하지 않는 한) O(n)의 연산 시간을 사용하는 선형 시간의 연산이 된다. 그러나 원소의 개수가 정해져 있고 변하지 않는다면 위와 같은 알고리즘도 상수 시간에 수행가능 하다고 말할 수 있다.