[알고리즘] 시간 복잡도¶

시간 복잡도란 프로그램의 입력 값과 실행 시간의 상관관계를 나타내는 척도로 알고리즘의 성능을 평가하기 위해 사용된다. 시간 복잡도를 사용하면 프로그램을 실행하지 않아도 알고리즘의 성능을 계산할 수 있고, 요구 조건을 충족하는 알고리즘을 선택할 수 있다.

Big-O 표기법¶

시간 복잡도는 주로 Big-O 표기법으로 표현한다. Big-O 표기법은 연산의 횟수가 다항식으로 표현될 경우, 계산의 편의를 위해 최고차항을 제외한 모든 항을 무시하는 방법이다. 이렇게 하는 이유는 n의 값이 충분히 크다면 최고차항의 영향력이 가장 크고, 나머지는 미미하기 때문이다.

예를 들어 어떤 알고리즘의 시간 복잡도가 5n³ + 3n의 식을 갖는다면 시간복잡도는 O(n³)이다.

시간 복잡도 비교¶

다음은 시간복잡도의 종류로, 위로 갈수록 실행 시간이 짧고, 아래로 갈수록 실행 시간이 길어진다. 참고로 log n은 log₂ n을 의미한다.

O(1): 상수 시간
O(log n): 로그 시간
O(n): 선형 시간
O(n log n): 선형 로그 시간
O(n^{^}2): 다차 시간
O(2^{^}n): 지수 시간
O(n!): 팩토리얼 시간

O(1)¶

상수 시간 복잡도는 입력 크기가 실행 시간에 영향을 미치지 못하는 것을 나타낸다.

a = 5
a += 1

O(log n)¶

로그 시간 복잡도는 실행 시간이 n의 로그에 비례한다는 것을 나타낸다. 예를 들어 n이 8이라면 log(8)은 3이다.

탐색해야 하는 데이터가 연산을 할 때마다 절반씩 줄어들 경우 O(log n) 시간 복잡도를 갖는다.

def binarySearch(data, n, target):
    start = 0
    end = n
    mid
    while end >= start:
        mid = (end + start) / 2
        if data[mid] == target:
            return 1
        else if data[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return 0

O(n)¶

선형 시간 복잡도는 입력 크기 n에 대해 실행 시간이 선형으로 증가하는 것을 나타낸다.

중첩 되지 않은 루프의 경우 O(n) 시간 복잡도를 갖는다.

for i in range(n):
    print(i)

O(n log n)¶

로그 선형 시간 복잡도는 실행시간이 n에 n의 로그를 곱한 형태로 증가하는 것을 나타낸다. 퀵 정렬이나, 병합 정렬이 n log n 시간 복잡도를 갖는다.

O(n²)¶

루프가 중첩될 경우 O(n²) 시간 복잡도를 갖는다.

for i in range(n):
    for j in range(n):
        print(i, j)

O(2ⁿ)¶

아래 코드는 각 재귀 호출마다 두 개의 재귀 호출이 발생하므로 O(2ⁿ) 시간 복잡도를 갖는다.

def fibo(n):
    if n == 1:
        return 0
    else if n == 2:
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)

O(n!)¶

아래 코드는 재귀 호출마다 n-1번의 재귀 호출이 발생하므로 O(n!) 시간 복잡도를 갖는다.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

코딩 테스트에서 시간 복잡도 활용하기¶

문제가 주어졌을 때 무작정 코드를 짜기보다는, 먼저 입력 값과 제한 시간을 읽어야 한다. 연산을 10⁸(1억)번 했을 때 1초 정도가 걸린다는 점을 이용하여 문제가 요구하는 알고리즘을 유추할 수 있다.

예를 들어 입력 값이 10,000 이하이고, 제한 시간이 1초인 문제가 있다고 가정하자. O(n²) 시간 복잡도를 갖는 알고리즘으로 문제를 풀 경우, 연산 횟수는 1억 회로 시간 초과에 걸리게 된다. 따라서 최소 O(n log n) 알고리즘으로 문제를 풀어야 할 것을 유추할 수 있다.

참조¶

https://www.nossi.dev/cote/timecomplexity
https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
https://www.youtube.com/watch?v=PFKPdjdWbQ8&ab_channel=%EC%A0%80%EC%84%B8%EC%83%81%EA%B0%9C%EB%B0%9C%EC%9E%90