시간 복잡도란?
시간 복잡도(time complexity):
- 알고리즘의 성능을 나타내는 지표
- 입력 크기에 대한 연산 횟수의 상한을 의미
- 낮으면 낮을 수록 좋음 ⏬
예를 들어 어떤 문제를 해결하는 알고리즘 A,B,C가 있을 때, 시간 복잡도가 가장 낮은 알고리즘이 A라면 A를 사용하는 게 좋다.
입력 크기란?
알고리즘이 처리해야 할 데이터 양이다. 책장의 꽂혀 있는 5권의 책을 정리해야 하는 문제라면 이때의 입력 크기는 5가 된다.
시간 복잡도를 측정하는 방법
시간 복잡도를 측정하는 방법은 앞서 언급한 '연산 횟수'와 관련이 있다. 즉, 시간 복잡도는 알고리즘이 시작한 순간부터 결과값이 나올 때까지의 연산 횟수를 나타낸다. 그리고 시간 복잡도를 측정한 결과는 다음과 같이 최선(best), 보통(normal), 최악(worst)의 경우로 나눈다.
그러나 특정 입력 크기에 한하여 연산 횟수를 기준으로 시간 복잡도를 측정할 수는 없다. 입력 크기는 매번 달라질 수 있기 때문이다. 다시 말해, 우리는 입력 크기를 N으로 일반화하여 연산 횟수의 추이를 나타내야 한다.
이런 방식으로 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다. 그리고 코딩 테스트에서의 시간 복잡도는 최악의 경우를 가정하는 것이 일반적이다.
빅오 표기법
최악의 경우 시간 복잡도를 표현하는 빅오 표기법
최악의 경우에 대해 시간 복잡도를 표현하는 방법은 무엇일까? 가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법이다. 그리고 이 표기법을 빅오 표기법(big-O notation)이라고 한다.
빅오 표기법이란, 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 차수를 지워 O(...)와 같이 표기하면 된다. 예를 들어서 어떤 프로그램의 연산 횟수가 f(x) = 2x² + 3x + 5라면 시간 복잡도를 O(x²)와 같이 표현하면 된다.
빅오 표기법의 표
점근 표기법이란 어떤 함수의 증가하는 추세를 표현하는 표기법입니다.
다만 점근 표기법은 이 책에서 자세히 설명하기는 적합하지 않으므로 이 정도만 이야기하겠습니다.
상한선은 빅오 표기법, 하한선은 빅오메가 표기법으로 표시합니다.
실제 코드에 적용해 본다면?
빅오 표기법의 식은 대체 어디서 나온 걸까?
def solution(n):
count = 0
# 반복문 1 : n²번 연산 수행
for i in range(n):
for j in range(n):
count += 1
# 반복문 2 : n번 연산 수행
for k in range(n):
count += 1
# 반복문 3 : 2*n번 연산 수행
for i in range(2*n):
count += 1
# 반복문 4 : 5번 연산 수행
for i in range(5):
count += 1
print(count) # 59(n이 6일 때, 6² + 6 + 2*6 + 5 = 59)
solution(6) # 함수 호출 solution() 함수는 주석 영역별로 각각 n², n + 2n, 5번의 증가 연산을 하며 결과값은 곧 연산 횟수를 의미한다. 주어진 함수 f(x)는 다음과 같이 표현한다.
f(x) = x² + 3x + 5
즉, 이 때의 시간 복잡도는 O(x²)라고 쓸 수 있다.
최고차항만 남기고 차수를 지우는 이유
앞서 빅오 표기법은 f(x)의 최고차항만 남기고 차수를 지워 O(...)와 같이 쓸 수 있다고 했다. 어떻게 이렇게 해도 되는지를 설명해보겠다.
f(x) = x² + 3x + 5에서 최고 차항인x²만 남김x²는 앞의 차수가 1이므로 제거할 것이 없음- 시간 복잡도는
O(x²)
다음은 x, x², x³를 비교한 그래프이다. 그래프를 보면 데이터가 커질수록 세 그래프의 차이는 확연하게 벌어진다. x값이 무한하게 커지면 그 격차는 더 심해질 것이다.
지수함수와 로그함수의 경우도 'x가 무한히 커진다'라는 것만 상상하면 쉽게 이해할 수 있다. 로그함수는 다항함수보다 느리게 증가하고, 지수함수는 다항함수보다 빠르게 증가한다. 그러므로 최고차항만 남기는 작업에서 우선 순위는 다음과 같을 것이다.
이 우선 순위대로면 다항함수와 로그함수가 섞여 있을 때 로그함수를, 지수함수와 다항함수가 섞여 있다면 다항함수를 지워야 할 것이다.
시간 복잡도를 코딩 테스트에 활용하기
이제 시간 복잡도를 표현하는 방식이 빅오 표기법이라는 건 알았다. 그럼 빅오 표기법을 어떻게 활용하면 좋을까? 코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있는지 확인해볼 수 있다. 그러면 문제 조건에 맞지 않는 알고리즘을 적용하느라 낭비하는 시간을 줄일 수 있다. 보통은 다음을 기준으로 알고리즘을 선택한다.
"컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다."
코딩 테스트의 문제는 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유있게 지정한다. 따라서 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 된다. 예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안 된다. 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 최대 연산 횟수는 다음과 같다.
맨 처음 우리가 살펴본 배열에서 검색하기로 돌아가보면...
이렇게 하나하나 짚어가며 찾는 방식은 시간 복잡도가 O(N)이다.. O(N)이 허용하는 연산 횟수는 1,000만이므로 데이터의 개수가 1,000만 개 이하면 이 알고리즘은 사용해도 된다. 바로 이렇게 시간 복잡도를 활용하여 불필요한 알고리즘을 제외하면 된다.
