<h1><center> 시간 복잡도(2) </center></h1>

###### tags: `💻 TIL`,`Algorithm`
###### date: `2023-12-3117:21:33.284Z`

> [color=#724cd1][name=데릭]
> [시간 복잡도](https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84)

# 개요

위키백과에 있는 시간 복잡도의 나머지에 대해 학습해보자.

## 서브-선형 시간(Sub-linear time)

$$T(n) = O(logn)^k$$

이런 식이 있다면, 이 알고리즘은 서브-선형시간동안 작동된다고 말할 수 있다. 특히 이 알고리즘은 이전 (1)에서 정의된 시간복잡도들을 포함하며,

$$O(n^{1/2})$$

Grover 탐색 알고리즘을 포함한다.

서브 선형 시간 동안 작동하는 전형적인 알고리즘은 병렬 프로세싱, 비표준 프로세싱을 사용하거나, 입력 구조에 대한 보장된 가정을 가진다. 그러나, 문자열의 처음부터 log(n)번째 비트 위치에서의 한 개의 비트를 갖는 모든 문자열의 집합과 같은 형식 언어는 입력의 모든 비트에 종속적일 수 있고, 서브-선형 시간에 가깝게 계산될 것이다.

서브-선형 시간 알고리즘이라는 특정 용어는 알고리즘들이 일렬 기계 모델에서 작동하며 입력에 대해 우선 가정을 허용하지 않는다는 점에서, 위와는 다른 알고르짐을 말한다. 그러나, 이 알고리즘들은 랜덤화 될 수 있고, 거의 가장 사소한 정도의 태스크들에 대해서는 반드시 랜덤화되어야만 한다.

이러한 알고리즘은 반드시 전체 입력을 읽지 않고 결과를 제공해야 하기 때문에, 이것의 특별함은 입력에 허용되는 접근에 굉장히 종속적이다.

$$b_1,...,b_k$$

보통 위와 같이 표현되는 이진 문자열에 대해서, 알고리즘이 어떤 i에 대해 b_i의 값을 요청하거나 얻는데 O(1)의 시간이 걸린다고 가정할 수 있다.

서브-선형 시간 알고리즘은 보통 랜덤화되며, 오로지 대략적인 해결책만을 제공해준다. 사실, 0만 가지는 이진 문자열의 특성은(비근사적인) 서브-선형 시간 알고리즘에 의해서 결정될 수 없다는 것을 쉽게 증명할 수 있다. 서브-선형 시간 알고리즘은 프로퍼티 테스팅(Property Testing) 조사에서 자연스럽게 나타난다.

## 선형 시간(Linear time)

만약 O(n)의 시간복잡도를 가진다면, 선형 타임을 갖는다고 말할 수 있다. 약식으로 충분히 큰 입력 크기에 대해서 수행시간이 입력 크기에 따라 선형적으로 증가함을 의미한다. 예를 들어, 리스트의 모든 요소를 더하는 프로서저는 리스트의 길이에 비례하는 시간을 요구한다. 이러한 설명은 수행시간이 특히 작은 n의 값에 대해 선형적인 비례형태로부터 상당한 편차를 가질 수 있기 때문에 다소 부정확하다.