복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다.
- 시간 복잡도(Time Complexity)는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
- 공간 복잡도(Space Complexity)는 특정한 크기의 입력해 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
같은 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.
보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립하여 메모리를 더 많이 사용하는 대신 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 이를 메모이제이션 기법이라고도 한다.
시간 복잡도
알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다.
코딩 테스트에서 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 '시간 초과' 판정을 받아 오답으로 처리된다.
시간 복잡도를 표현할 때는 빅오(Big - O) 표기법을 사용한다.
점근적 상한(Asymptotic Upper Bound)라고 불리는 빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법으로 함수의 상한만을 나타낸다. 예를 들어 연산 횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘이 있을 때 시간 복잡도를 빅오 표기법으로 나타내면 O(N^3)이 된다.
시간 복잡도 관련 알고리즘 설계 Tip
코딩 테스트 문제에서 시간 제한은 1 ~ 5초가량이다. 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억이 넘어가는 경우 C언어를 기준으로 1 ~ 3초가 소요되고 Python 기준으로 5 ~ 15초가 소요된다.
이처럼 시간 복잡도 분석은 문제 풀이의 핵심이기 때문에 알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 조건을 먼저 보고 얼마나 효율적인 알고리즘을 작성해야 하는지 먼저 생각한다.
파이썬의 경우 일반적으로 1초에 20,000,000 번의 연산을 할 수 있다고 가정하고 알고리즘을 설계하면 무리 없이 문제를 풀 수 있다.
시간 제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다.
- N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
수행 시간 측정 소스코드
import time
start = time.time() # 측정 시작
# 프로그램 소스코드
end = time.time() # 측정 종료
print("수행 시간:", end - start) # 수행 시간 출력공간 복잡도
공간 복잡도를 표기할 때도 시간 복잡도와 마찬가지로 빅오 표기법을 이용한다.
다만, 앞서 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다.
일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.
- int a[1000]: 4KB
- int a[1000000]: 4MB
- int a[2000][2000]: 16MB
위는 고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량이다.
코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다. 다시 말해 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다는 의미이다.
파이썬에서는 int 자료형이 없지만 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 드물다.
알고리즘 문제 해결 과정
- 지문 읽기 및 컴퓨팅적 사고
- 요구사항(복잡도) 분석
- 문제 해결을 위한 아이디어 찾기
- 소스코드 설계 및 코딩
참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| [알고리즘 이론] 최단 경로 알고리즘(1) - 다익스트라 최단 경로 알고리즘 (0) | 2022.02.23 |
|---|---|
| [알고리즘 이론] 다이나믹 프로그래밍(Dynamic Programming) (0) | 2022.02.05 |
| [알고리즘 이론] 이진 탐색(Binaray Search) (0) | 2022.02.02 |
| [알고리즘 이론] 정렬 알고리즘(Sorting Algorithm) (0) | 2022.01.24 |
| [알고리즘 이론] 탐색 알고리즘 - DFS / BFS (0) | 2022.01.14 |