선형 시간

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

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

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

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

입력값의 전체를 보지 않고서는 결과를 얻을 수 없는 문제는, 입력을 전부 읽어내는 것만으로도 선형시간이 걸리기 때문에, 아무리 적어도 선형시간 이상 걸리게 된다.

같이 보기

• 다항 시간 (polynomial time)
• 지수 시간 (exponential time)
• 정수 시간

각주

1. 예: 연상 메모리(content-addressable memory)와 같이 문제의 병렬성을 응용한 하드웨어 기술