How have Yoobin?
본 글은 [코딩테스트 합격자 되기]의 'CH 3. 알고리즘의 효율 분석하기'를 참고하여 작성한 글입니다.
시간 복잡도(Time Complexity)란?
- 알고리즘의 성능을 나타내는 지표
- 입력 크기(알고리즘이 처리해야 할 데이터의 양)에 대한 연산 횟수의 상한을 의미
- 시간 복잡도는 낮으면 낮을수록 좋다.
코드의 성능을 측정하는 방법 2가지
- 코드의 성능은 코드를 돌리는 데 필요한 메모리(공간)와 걸리는 시간이 결정한다.
절대 시간 측정
- 아래와 같이 프로그램을 작성한 다음 결과가 나올 때까지의 시간을 측정할 수 있음 → 실행환경에 따라 측정 시간이 달라질 수 있어 잘 사용 X
import math
import time
import datetime
start = time.time()
n = 0
for i in range(1, 7):
n += i
print(n)
end = time.time()
sec = (end - start)
result = datetime.timedelta(seconds=sec)
print(result)
result_list = str(datetime.timedelta(seconds=sec)).split(".")시간 복잡도 측정
- 시간 복잡도는 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 나타낸다.
- 시간 복잡도의 결과는 최선, 보통, 최악으로 나뉜다. 예를 들어 배열에서 값을 찾는 경우 최선의 경우는 검색을 시작하는 위치에 찾는 값이 나오는 것, 최악의 경우는 배열에 찾는 값이 없는 것이다. 예를 들어 배열의 크기가 8이면 최선은 1번, 최악은 8번 이런 식으로 특정 연산 횟수를 기준으로 시간복잡도를 이야기 하는 것은 안되니까 입력 크기 n에 대해 시간 복잡도를 표현 하자
- 점근적 표기법 : 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법
- 빅오 표기법: 상한선을 사용
- 빅 오메가 표기법: 하한선을 사용
빅오 표기법 (Big O Notation)
- 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 차수를 지워 O(…)로 표기
def solution(n):
count = 0
# 반복분 1 : n^2번 연산함
for i in range(n): # n번 연산 -> n
for i in range(n): # n번 연산 -> n x n
count += 1
# 반복문 2: n번 연산 수행
for k in range(n):
count += 1
# 반복문 3: 2n번 연산 수행
for i in range(2*n):
count += 1
# 반복문 4: 5번 연산 수행
for i in range(5):
count += 1
print(count)
solution(6) # 59번 연산을 하게 됨
- solution() 함수를 식으로 표현하면 아래와 같이 되므로, Big O notation은 최고 차항만 남긴 O(n^2)
- 특정 x 시점 이후부터 항상 f(x) ≤ C * g(x) (C는 상수)를 만족할 때, f(x)의 최악의 시간 복잡도는 O(g(x)) → g(x)에 상수 C를 곱했을 때 특정 시점부터 f(x)를 넘어서는지의 여부를 보면 된다.
$$ f(x) = x^2 + 3x + 5 $$
- 증가하는 속도: 지수함수 > 다항함수 > 로그함수
- 시간복잡도: (Bad) 지수함수 > 다항함수 > 로그함수 (Good)
시간 복잡도를 코딩테스트에 활용하기
-
- 보통은 컴퓨터가 초당 연산할 수 있는 최대 횟수가 1억번이라는 것에 기초하여 알고리즘을 선택
- 연산 횟수를 1000 ~ 3000만 정도로 고려해서 시간 복잡도를 생각 → 제한 시간이 1초라면 연산 횟수가 3000만 번이 넘어가면 안됨
- 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 최대 연산 횟수 → 시간복잡도가 낮아질수록 같은 시간에 더 많은 연산을 할 수 있다!빅오 표기법으로 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 지 확인해볼 수 있다!
시간 복잡도 최대 연산 횟수 O(N!) 10 O(2^n) 20 ~ 25 O(N^3) 200 ~ 300 O(N^2) 3,000 ~ 5,000 O(NlogN) 100만 O(N) 1,000 ~ 2,000만 O(logN) 10억
시간 복잡도 예시
별 찍기 문제의 시간 복잡도
for i in range(N):
print("*" * i) # 출력 자체가 연산이므로 i번 연산하는 것이 1 ~ N까지 수행된다.
# 결과
* # 1번 연산
** # 2번 연산
*** # 3번 연산
.
.
.
****** .... ***** # N번 연산
- 모든 연산 횟수를 총합해야 하므로 f(x)는 다음과 같은 빅오 표기법을 가진다.
$$ f(x) = \frac{N(N+1)}{2}\\ \therefore{O(N^2)} $$
박테리아 수명 문제
- 초기 박테리아 세포 개수가 N일 때마다 세포 개수가 이전 세포 개수의 반으로 줄어든다면 언제 모든 박테리아가 죽을까?
$$ Bacteria\ now = N \\ Bacteria\ after\ 1\ year = \frac{1}{2}N \\ Bacteria\ after\ Y\ years = (\frac{1}{2})^YN \\ $$
- 박테리아의 소멸 시기: (1/2)^Y * N ≤ 1 일 때의 Y 값이며, 다음과 같은 빅오 표기법을 가진다
$$ (\frac{1}{2})^YN \le 1 \\ N \le 2^Y\\ log_2N \le Y \\ \therefore{O(logN)} $$
- 특정값을 계속 X 1/2 한다면 시간복잡도를 O(logN)이라 생각하자!
각 알고리즘에 따른 빅오 표기법
흠... 문제 풀 때는 딱히 시간 복잡도를 고려하지 않고 푸는데 이런 것들도 다 생각해야 하는구나.. 학교 수업에서 들을 때에는 어느 정도 이해가 됐었고, 계산하는 문제까지는 풀 수 있었는데 코테에서 사용하는 알고리즘에 직접 적용해서 생각해야 한다고 하니 영 감이 안 잡힌다.