📚복잡도
복잡도는 알고리즘의 성능을 나타내는 척도이다.
시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
결국 동일하게 수행하는 알고리즘이 있다면 일반적으로는 복잡도가 낮을수록 좋은 알고리즘이라고 말할 수 있다.
🔍시간 복잡도
시간 복잡도를 표현할 때는 보통 빅오(Big-o)표기법을 사용한다.
빅오 표기법을 간단히 정의하면 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타낸다.
[예제 1] 시간 복잡도 O(N)
array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)
summary = 0 # 합계를 저장할 변수
# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
summary += x
# 결과를 출력
print(summary)[예제 1]에서는 5개의 데이터를 받아 차례로 5번 더해준다(N = 5). 이때 연산 횟수는 N에 비례하는 것을 알 수 있음.
따라서 이 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간복잡도를 O(N) 이라고 표기한다.
[예제 2] 시간 복잡도 O(1)
a = 5
b = 7
print(a + b)[예제 2]에서는 a와 b에 값을 대입하는 대입 연산과 출력 함수를 배제하고 보면, 이 소스코드의 연산 횟수는 1이다.
따라서 이는 상수 연산이므로 시간 복잡도를 O(1) 로 표기할 수 있다.
[예제 3] 시간 복잡도 O(N²)
array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)
for i in array:
for j in array:
temp = i + j
print(temp)[예제 3]에서는 2중 반복문을 이용하여 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문에
데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N²) 의 시간 복잡도를 가진다.
사실은 간단한 2중 반복문이기 때문에 N X N만큼의 연산이 필요하다는 것을 유추해볼 수 있다.
하지만 그렇다고 해서 모든 2중 반복문의 시간 복잡도가 O(N²)은 아니다. 만약 소스코드가 내부적으로 다른 함수를 호출한다면
내부 함수의 시간 복잡도까지 고려해야 한다.
따라서 소스코드를 정확하게 분석한 뒤에 시간 복잡도를 계산해야 한다는 점을 기억하자.
다음은 자주 등장하는 시간 복잡도 표인데, 위쪽에 있을수록 더 빠르다.
| 빅오 표기법 | 명칭 |
|---|---|
| O(1) | 상수 시간(Constant time) |
| O(logN) | 로그 시간(Log time) |
| O(N) | 선형 시간 |
| O(NlogN) | 로그 선형 시간 |
| O(N2) | 이차 시간 |
| O(N3) | 삼차 시간 |
| O(2n) | 지수 시간 |
일반적으로 코딩 테스트 환경에서는 O(N3)을 넘어가면 문제 풀이에서 사용하기 어렵다.
왜냐하면 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C 언어를 기준으로 통상 1초 이상의 시간이 소요된다. 이때 N의 크기가 5,000이 넘는다면 족히 10초 이상의 시간이 걸릴 수 있는데, 특히 파이썬은 더욱 오래 걸리며, 코딩 테스트 문제에서 시간 제한은 1 ~ 5초 가량이므로 보통 연산 횟수가 10억을 넘어가면 오답 판정을 받을 수 있다.
<시간 제한이 1초인 문제에 대한 예시>
- N의 범위가 500인 경우 : 시간 복잡도가 O(N3)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우 : 시간 복잡도가 O(N2)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
🔍공간 복잡도
공간 복잡도도 시간 복잡도와 마찬가지로 빅오 표기법을 이용한다.
코딩 테스트 대부분의 문제들은 다수의 데이터에 대한 효율적인 처리를 요구하기 때문에 대부분 리스트(배열)을 사용하여 풀어야 한다.
정수형 자료형인 int 를 기준으로 리스트 크기에 따른 메모리 사용량은 다음과 같다.
- int a[ 1000 ] : 4KB
- int a[ 1000000 ] : 4MB
- int a[ 2000 ][ 2000 ] : 16MB
코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다. 즉, 일반적인 경우에서 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다는 의미이다.
🔍시간과 메모리 측정
파이썬에서는 특정 프로그램의 수행 시간과 메모리 사용량을 측정할 수 있다.
다음은 특정 프로그램의 수행 시간을 측정하는 소스코드 예시이다.
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행 시간 출력
※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.