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

###### tags: `💻 TIL`,`Algorithm`
###### date: `2023-12-3017: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)

# 개요

오늘은 그 동안 띄엄띄엄 알고만 있던 개념인 시간 복잡도에 대해 학습해보자.

## 시간 복잡도

계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

시간 복잡도는 주어진 알고리즘이 입력 데이터의 크기에 따라 얼마나 빠르게 실행되는지를 나타내는 개념이다. 이를 표현할 때, 주로 Big-O 표기법이 사용된다.

예로 들어, 크기가 n인 모든 입력에 대해 알고리즘이 수행하는 기본 연산의 개수를 세어서 알고리즘의 시간 복잡도를 예측할 수 있습니다. 이때, Big-O 표기법은 알고리즘의 최악의 경우(상한)에 대한 시간 복잡도를 나타냅니다.

알고리즘의 수행 시간은 동일한 크기의 다양한 입력에 따라 다를 수 있기 때문에, T(n)으로 표현되는 크기 n의 입력에 대한 알고리즘의 최대 실행 시간을 정의합니다.

또한, 평균 시간 복잡도는 보다 덜 흔하지만 명확하게 설명된 측정 방법 중 하나로, 알고리즘의 평균 실행 시간을 나타냅니다.

마지막으로, 시간 복잡도는 함수 T(n)의 특성에 따라 분류됩니다. 예를 들어, T(n) = O(n)인 알고리즘은 `선형 시간 알고리즘`이라고 부르며, 어떤 M >= n > 에 대해 T(n) = O(Mn)이고 Mn = O(T(n))인 알고리즘은 `지수 시간 알고리즘`이라고 합니다.

**NOTE**

> Big-O: 알고리즘의 성능을 대략적으로 표현하는 방법 중 하나로, 알고리즘의 실행 시간을 입력 크기에 따라 얼마나 빨리 늘어나는지 나타내는 것이다. <br>
> 상한은 최악의 경우에 대한 예측으로, 입력이 커질수록 알고리즘의 실행 시간이 어떤 정도로 증가할지를 제한적으로 나타내는 것이다. Big-O 표기법은 이런 관계를 간단한 기호로 나타내어 알고리즘의 효율성을 대략적으로 비교할 수 있게 해주는데, 이때 낮은 차수의 항과 상수를 무시하여 주된 영향을 주는 항만을 고려한다.

## 시간 복잡도 표


## 상수 시간 (Constant time)

만약 어떤 알고리즘의 T(n)값이 입력 크기에 구애받지 않는 값에 한정된다면, 이 알고리즘은 상수 시간( O(1) 시간 복잡도라고 쓰기도 한다.)이라고 말할 수있다.

예를 들어, 단 하나의 연산이 어떤 배열에서의 item 위치를 알아내는 것을 수행한다고 할 때, 이 item에 접근하는 것은 상수 시간만큼 걸린다.

그러나 순서가 정해져있지 않은 배열에서의 최소 값을 찾는 것은, 가장 작은 값을 결정하기 위해 어떤 배열에서의 각 item을 훑는 것이 필요하기 때문에 상수 시간이 아니다. 이런 경우, 선형 시간 연산이라고 하며, O(n)의 시간 복잡도를 가진다.

만약 item의 개수를 미리 알고 있고 변화(수정, 추가)가 없다면, 이런 알고리즘은 상수 시간에 이루어질 수 잇다고 말할 수 있다.

상수 시간이라는 이름에도 불구하고, 수행시간은 문제의 크기에 독립적일 필요가 없지만 수행시간의 상한은 문제의 size에 독립적으로 제한된다.

만약에 T(n)이 O(어떤 상수값)이라면, T(n)은 O(1)이다는 것이 표준 표기법이다.

## 로그 시간(Logarithmic time)

만약에 T(n) = O(log n)이라면, 이 알고리즘은 로그 시간이 걸린다는 의미이다. 컴퓨터는 이진수 시스템을 사용하기 때문에 로그는 밑을 대부분 2로 사용한다.

$$log_2n$$

때때로 logn으로도 쓰인다. 그러나 로그의 밑이 변할 때,

$$log_an, log_bn$$

두 개는 오로지 상수 승수에 따라서만 달라지며 이런 것들은 Big-O 표기법에서는 생략한다.

$$logn$$

그러므로

O(logn)은 로그의 밑과 상관없이 로그 시간 알고리즘에 대한 표준 표기법이 된다.

로그시간이 걸리는 알고리즘은 이진트리에서의 연산에서나 이진 탐색에서 찾아볼 수 있다.

O(logn)의 시간 복잡도를 갖는 알고리즘은 입력 크기 n에 비례하여 logarithmic하게(입력 크기에 비례하여 로그 함수 형태로 증가한다는 의미) 증가하는 실행 시간을 가지는데, 이는 매우 효율적이라고 여긴다.

가장 쉬운 예제 알고리즘은, 문자열을 절반으로 쪼개어 쪼갠 문자열 중 오른쪽 문자열을 다시 또 절반으로 쪼개고, 이를 반복하는 알고리즘이 있다. 이 알고리즘은 각 단계에서 입력 크기를 절반으로 줄이기 때문에 O(logn)의 시간 복잡도를 가진다.(n은 문자열의 길이) 각 단계에서는 입력의 크기가 반으로 감소하므로 문자열의 길이가 n일 때, 계속 쪼개져 1이 되는 형태이다. 이런게 로그 함수의 성질 때문이고 O(logn)으로 표현한다.

let description = "한국에서 코딩하는 iOS 개$$T(n$$

func right(_ str: String) {
    let length = str.count 
    
    func help(_ index: Int) {
        if index < length {
        
        // 인덱스로 배열 끝까지해서 문자열 출력
        let substring = String(str.suffix(from: str.index(str.startIndex, offsetBy: index)))
        print(substring)
        
        // 재귀 호출 부분 : 오른쪽의 절반에 대해서 help를 호출
        help(Int(ceil(Double(length + index) / 2)))
        }
    }
    
    help(0)
}

right(description)

## 다항 로그 시간(Polylogarithmic time)

$$T(n) = O(logn)^k$$
위의 식이라면, 알고리즘은 어떤 상수 k에 대해 다항 로그 시간 동안 수행된다고 말할 수 있다. 예를 들어, 행열 체인 곱은 병렬 랜덤 접근 기계(Parallel Random Access Machine: PRAM)에서 다항 로그 시간 안에 해결할 수 있다.