선형 시간 문서 원본 보기

{{위키데이터 속성 추적}}
'''선형 시간'''(線型時間, Linear time)이란, [[계산 복잡도 이론]]에서, 입력의 길이 <math>n</math>에 대하여, 어떤 [[알고리즘]]의 실행시간이 [[선형성|선형]]([[점근 표기법|<math>{\color{Blue}O}(n)</math>]])이 되는 것을 뜻한다.
예를 들면, 입력된 숫자열의 총합을 계산하는 순서는 숫자열의 길이에 비례하는 시간이 필요하다.

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

선형시간의 알고리즘이 가능하면 바람직한 것으로 받아들여지는 경우는 많다. 선형시간에 거의 가까운 알고리즘이나, 보다 좋은 알고리즘을 찾아내기 위한 연구는 현재까지 이루어져왔다. 이 연구는 소프트웨어 뿐만 아니라 하드웨어 적인 수단 또한 포함되어 있다. 하드웨어의 경우, 표준적인 계산 모델에서는 선형시간을 얻어낼 수 없는 알고리즘을 선형시간으로 수행하는 것이 가능한 경우가 있다.<ref>예: [[연상 메모리]](content-addressable memory)와 같이 문제의 병렬성을 응용한 하드웨어 기술</ref>

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

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

== 같이 보기 ==
* [[다항 시간]] (polynomial time)
* [[지수 시간]] (exponential time)
* [[정수 시간]]

== 각주 ==
<references/>

[[분류:계산 복잡도 이론]]