선형 시간

선형 시간(線型時間, Linear time)이란, 계산 복잡도 이론에서, 입력의 길이 $n$ 에 대하여, 어떤 알고리즘의 실행시간이 선형( ${\color {Blue}O}(n)$ )이 되는 것을 뜻한다. 예를 들면, 입력된 숫자열의 총합을 계산하는 순서는 숫자열의 길이에 비례하는 시간이 필요하다.

이상의 설명은 어디까지나 이론적인 것으로, 실제의 실행시간은(특히 $n$ 이 비교적 작은 경우) 입력의 길이에 정확하게 비례한다고 볼 수는 없다. 기술적으로 충분히 큰 n에 대하여, 알고리즘의 실행시간이 $an$ 에서 $bn$ 의 범위 안에 들 경우 ( $a$ 와 $b$ 는 양의 정수), 이를 '선형 시간'이라고 부를 수 있다. 자세한 이론은 점근 표기법을 참조할 것.

선형시간의 알고리즘이 가능하면 바람직한 것으로 받아들여지는 경우는 많다. 선형시간에 거의 가까운 알고리즘이나, 보다 좋은 알고리즘을 찾아내기 위한 연구는 현재까지 이루어져왔다. 이 연구는 소프트웨어 뿐만 아니라 하드웨어 적인 수단 또한 포함되어 있다. 하드웨어의 경우, 표준적인 계산 모델에서는 선형시간을 얻어낼 수 없는 알고리즘을 선형시간으로 수행하는 것이 가능한 경우가 있다.^[1]

예를 들어, 정렬 알고리즘의 경우, 입력이 되는 숫자열에 따라 선형시간으로 정렬이 가능한 경우도 있으나, 숫자열의 각 항목 사이의 비교를 기반으로 한 정렬 알고리즘의 경우는 일반적으로 $O(n\log n)$ 보다 시간을 단축시킬 수 없다. 이러한 복잡도 증명은, 점근 표기법이 보는 대상이며, 일반적으로 정렬 알고리즘은 $\Omega (n\log n)$ 라고 말할 수 있다. 같은 식으로, 무작위로 생성된 길이 $n$ 의 숫자의 배열에서 최대치를 찾아내는 선택 알고리즘(Selection Algorithm)은 최대치를 찾는데 적어도 ( $n-1$ )회의 비교가 필요하다는 것을 논리적으로 볼때 알 수 있으며, $\Omega (n)$ 이 된다.