![[Algorithm] 복잡도(Complexity)](/_next/image?url=https%3A%2F%2Fblog.huns.site%2Fimgs%2Fthumbnails%2Fblog%2Fposts%2Fcomputer-science%2Falgorithm.png&w=1200&q=75)
TOC
복잡도
- 알고리즘의 성능을 나타내는 척도
- 시간복잡도와 공간 복잡도로 구분한다.
1. 시간 복잡도
-
특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
-
알고리즘을 위해 필요한 연산의 횟수
-
알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 시간 복잡도 의미
-
프로그램을 효율적으로 작성해야 프로그램이 시간 제한 내에 동작할 수 있다.
1.1. 표기법 'Big-O'
-
가장 빠르게 증가하는 항만을 고려하는 표기법
-
즉, 함수의 상한만을 나타낸다.
-
시간 복잡도 분석은 문제 풀이의 핵심
-
문제의 조건을 먼저 확인하여 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 먼저 파악할 것
1.2. Big-O 활용예제 1
array = [3,5, 1, 2, 4] # 5개의 데이터(N=5)
summary = 0 # 합계를 저장할 변수
# 모든 데이터를 하나씩 확인하면서 합계를 계산
for x in array:
summary += x
# 결과를 출력
print(summary)
실행결과는 다음과 같다.
15
위의 예제는 5개의 데이터를 받아 차례로 5회 더해준다.(N=5) 즉, 연산횟수는 N에 비례한다.
본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간 복잡도를 O(N)이라고 표기한다.
1.3. Big-O 활용예제 2
다음 예제는 어떤 시간 복잡도를 가질까.
a = 5
b = 7
print(a+b)
대입 연산과 출력 함수를 무시하면, 이 소스코드의 연산 횟수는 1이다. (더하기 연산 한 번) 이는 상수 연산으로, 시간 복잡도는 'O(1)'로 표현할 수 있다.
1.4. Big-O 활용예제 3
- 다음 예제는 어떤 시간 복잡도를 가질까.
array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5)
for i in array:
for j in array:
temp = i * j
print(temp)
- 이 소스코드는 데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N²)의 시간 복잡도를 가진다. 2중 반복문이기 때문이다.
- 모든 2중 반복문의 시간 복잡도가 O(N²)인 것은 아니다. 내부 함수가 있는 경우 내부 함수의 시간 복잡도도 고려해주어야 한다.
- 퀵 정렬(6장에서 학습)의 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 시간 복잡도는 O(N²)이다.
- 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.
1.5. 시간 복잡도 표
- 위쪽에 있을수록 더 빠르다.
| 빅오 표기법 | 명칭 |
|---|---|
| O(1) | 상수 시간(Constant time) |
| O(logN) | 로그 시간(Log time) |
| O(N) | 상수 시간(Constant time) |
| O(N²) | 이차 시간 |
| O(N³) | 삼차 시간 |
| O(2ⁿ) | 지수시간 |
1.6. 빅오 표기법의 한계
- 빅오 표기법이 항상 절대적인 것은 아니다.
- 실제 코딩테스트에서는 차수가 작은 항들을 완전히 무시하는 것도 곤란
3N³ + 5N² + 1,000,000인 알고리즘의 경우
빅오 표기법에서는 차수가 가장 큰 항만 남기 때문에 O(N³)으로 표기
하지만, 실제로 N이 작을 때는 상수 값인 1,000,000의 영향력이 크다.
1.7. 시간복잡도에 따른 알고리즘 선택
- N의 범위가 500인 경우 : 시간복잡도가 O(N³)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우 : 시간복잡도가 O(N²)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
2. 공간복잡도
-
특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
-
알고리즘을 위해 필요한 메모리의 양
-
시간 복잡도처럼 빅오 표기법을 이용
-
코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문
-
정수형 자료인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자.
- int a[1000]: 4KB
- int a[1000000]: 4MB
- int a[2000][2000]: 16MB
-
코딩테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 즉, 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미
3. 시간과 메모리 측정
- 다음의 코드를 통해 프로그램 수행 시간을 측정할 수 있다.
* 수행 시간 측정 소스코드
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time().time() # 측정 종료
# 수행 시간 출력
print("time :", end_time - start_time)
3.1. 예시
- '선택 정렬'과 '파이썬 기본 정렬 라이브러리'의 속도 비교
- '선택 정렬' : 최악의 경우 O(N²)
- '기본 정렬 라이브러리' : 최악의 경우 O(NlogN)
from random import *
import time
# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수
# 선택 정렬 프로그램 성능 측정
start_time = time.time()
# 선택 정렬 프로그램 소스코드
for i in range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
# 스와프
array[i], array[min_index] = array[min_index], array[i]
end_time = time.time() # 측정 종료
# 수행시간 출력
print("선택 정렬 성능 측정: ", end_time - start_time)
# 기본 정렬 라이브러리 성능 측정
start_time = time.time()
# 기본 정렬 라이브러리 사용
array.sort()
end_time = time.time() # 측정 종료
# 수행시간 출력
print("기본 정렬 라이브러리 성능 측정: ", end_time - start_time)
출력값은 다음과 같다.
선택 정렬 성능 측정: 3.139763116836548
기본 정렬 라이브러리 성능 측정: 0.0
즉, 이렇게 알고리즘의 성능을 측정하기 위해서 시간 측정 라이브러리를 사용하는 습관을 기르는 것이 좋다.
4. 번외
- 메모리를 더 소모하는 대신 얻을 수 있는 시간적 이점이 매우 큰 경우가 있다.
- 메모이제이션(Memoization)
- 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법
- 8장에서 더 다룰 예정
REFERENCES
- 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 한빛미디어
