[Algorithm] 시간 복잡도 (Time Complexity)
1. 시간 복잡도 및 표기법
시간 복잡도는 특정 코드가 있을 때, 해당 코드에서 특정한 입력이 주어졌을 때, 얼마나 많은 연산을 하는지에 대한 개념을 나타낸 것이다.
알고리즘마다 특정 값에 대한 참조, 연산이 많을수록 당연히 복잡도가 다르고, 때에 따라서는 비효율적인 알고리즘이 될 수 있기에 우수한 성능을 낼 수 있는 알고리즘을 구현하기 위해서는 시간 복잡도를 정확하게 이해하고 알고리즘을 설계할 필요가 있다.
시간 복잡도를 표기하는 방법에는 아래의 3가지가 존재한다.
1) 빅 오(Big O) 표기법
빅 오(Big O) 표기법은 알고리즘의 실행 시간을 최악의 경우의 시간 복잡도로 나타내는 데 사용된다.
어떤 알고리즘의 시간 복잡도가 O(f(n))이라면, 해당 알고리즘의 실행 시간은 입력 크기 n이 증가함에 따라 f(n)의 상수 배만큼 증가하는데, 이는 알고리즘의 상한을 나타내는 데, 더 이상의 연산 시간의 증가가 필요하지 않다는 것을 의미한다.
2) 빅 오메가(Big Ω) 표기법
빅 오메가(Big Ω) 표기법은 빅 오 표기법과 반대로, 알고리즘의 실행 시간을 최선의 경우의 시간 복잡도로 나타내는 데 사용된다.
어떤 알고리즘의 시간 복잡도가 Ω(g(n))이라면, 해당 알고리즘의 실행 시간은 입력 크기 n이 증가함에 따라 g(n)의 상수 배만큼 증가하는데, 이는 알고리즘의 하한을 나타내고, 이는 연산의 시간이 더 줄지 않는다는 것을 의미한다.
3) 빅 쎄타(Big Θ) 표기법
빅 쎄타 표기법은 알고리즘의 실행 시간을 평균적인 경우의 시간 복잡도로 나타내는 데 사용된다.
어떤 알고리즘의 시간 복잡도가 Θ(h(n))이라면, 해당 알고리즘의 실행 시간은 입력 크기 n이 증가함에 따라 h(n)의 상수 배만큼 증가하며, 동시에 h(n)의 하한도 적어도 상수 배만큼 증가하는데, 이는 어느 쪽에도 치우치지 않고 평균 적으로 제한되어 있다는 것이다.
2. 시간 복잡도 종류
시간 복잡도가 어느 정도 될 것이라는 표기는 별도로 존재하며, 일반적으로 최악의 상황인 빅오(Big O) 표기법을 기반으로 나타낸다.
아래는 많이 사용되는 시간 복잡도의 종류를 나타낸 것이며 시간이 짧은 순으로 알아볼 것이다.
1) O(1)
첫 번째의 사례는 연산에 대하여 동일한 시간을 요하는 것이고, 어떠한 N(입력 값)이 들어와도 1이 걸린다는 것이다.
이는 Hash Map과 같은 자료구조에서 특정 Key에 대한 Value를 가져오거나, List의 Index를 기반으로 값을 가져오는 부분에 있어서 이와 같은 시간 복잡도를 가질 수 있다.
2) O(n)
두 번째의 사례는 N(입력 값)에 대한 시간 복잡도를 가지는 것인데, 이는, For 문과 같이 Array를 Break 없이 모든 원소에 대하여 순환하여 참조하였을 때, N과 같은 시간 복잡도를 가질 수 있는 것을 예로 들 수가 있다.
3) O(log n)
세 번째의 사례로 N(입력 값)이 주어졌을 때, log n의 시간 복잡도를 가진다는 것인데, 이는, 이분 탐색의 알고리즘에 적용할 수 있다.
- 이분탐색 예시 : 해당 인덱스의 값을 원소가지는 1~9 크기의 Array에서 7을 찾는 Case
- Array의 5의 인덱스(Array 절반 위치)를 조회
- 찾는 값과 일치 여부 또는 대소 비교
- 찾는 값이 아니면 Array를 분할하여 다시 1번 로직으로 조회
- Array 분할 시 5가 찾는 값(7)보다 작기 때문에 6~9의 Array로 분할
4) n * O(log n)
네 번째의 사례로 N(입력 값)이 주어졌을 때, log n에서 N만큼의 시간 복잡도를 필요로 한다는 것인데, 이는 이분 탐색과 해당 Array를 순회하는 로직이 있을 때, 이와 같은 시간 복잡도를 가질 수 있다.
5) O(n**2)
시간 복잡도에서 N(입력 값)의 제곱을 필요로 하는 알고리즘은 대부분 For 문을 2번 순회하는 것으로 예시를 들 수 있다.
1~5의 원소를 가지고 있는 Array를 2번 순회한다고 하면 5(원소의 개수) * 5(원소의 개수)가 되고, 이는 N ** 2가 되는 것이다.
6) O(2**n)
이번 2**n과 같은 사례는 종이 접기를 예로 들 수가 있는데, 종이는 반으로 접을수록 두께는 2배씩 된다는 성질을 가지고 있다.
해당 예시로, 피보나치 수열을 들 수가 있고, 이는 수가 커질수록 연산이 기하급수적으로 늘어날 수 있다는 것을 볼 수 있다.
7) O(n!)
마지막으로 팩토리얼인데, 이는 N이 5일 때, 1*2*3*4*5를 나타내는 것으로, 가장 높은 시간 복잡도를 가진다.
확률과 통계 부문에서 팩토리얼을 자주 이용하게 되는데, 시간 복잡도에 주의하여 코드를 구현할 필요가 있다.