알고리즘 효율 분석: 시간 복잡도

1. 시간 복잡도

what?

입력 크기에 따른 연산 횟수

알고리즘의 성능을 나타내는 지표

낮으면 낮을 수록 좋다.

 

why?

문제를 해결하는 방법에는 여러 가지가 있을 수 있다. 그 중에서 가장 효율적인 해결방법은 연산시간이 제일 적게 소요되는 것이다. 각 알고리즘의 효율을 비교하기 위해 사용한다.

 

how?

빅오 표기법 사용

빅오 표기법

what?

함수의 증가 양상 표기법. 알고리즘의 최악의 실행시간을 표시한다.

 

결과값이 연산 한 번만에 나올 수도 있고 최대 N번의 연산을 해야 나올 수도 있다고 할 때, 'N'을 최악의 연산 횟수라고 한다. 코딩 테스트에서 시간 복잡도는 일반적으로 최악의 경우를 가정해서 말한다.(모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 함)

 

how?

어떤 프로그램의 연산 횟수를 f(x)라고 할 때

함수의 최고차항을 남기고 계수를 지운다.

프로그램의 연산 횟수가
f(x) = 2x^2 + 3x + 5
일 경우,
시간 복잡도는
O(x^2)

 

표기 우선순위(증가폭이 큰 것을 적음)

지수함수>다항함수>로그함수

 

활용 방법

제한시간이 1초인 경우 연산 횟수는 3000만 번까지

1초당 N 가용범위

시간 복잡도	N의 가용 범위
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)	1000~2,000만
O(logN)	10억

 

쉬운 문제를 풀더라도 시간 복잡도를 먼저 따져보면서 습관을 들여놓는 것이 좋다.

 

 

2. 시간 복잡도 계산하기

문제 정의 → 연산 횟수 측정 → 시간 복잡도 분석

 

1)별 찍기

숫자 N을 입력받으면 N번째 줄까지 별을 1개부터 N개까지 늘려가며 출력하기

 

입출력 예시

N = 3	N = 5
* ** ***	* ** *** **** *****

 

연산 횟수 구하기

1번째 줄: 1번 연산

2번째 줄: 2번 연산

N번째 줄: N번 연산

 

시간 복잡도 분석

f(N) = 1 + 2 + ... + N = N(N+1)/2

∴ O(N^2)

 

2)박테리아 수명

 

초기 박테리아 세포 개수가 N개일 때 해마다 세포 개수가 이전 세포 개수의 반으로 줄 경우, 언제 모든 박테리아가 죽는지 계산하기

 

입출력 예시

N = 16

5

 

연산 횟수 구하기

현재 박테리아의 수가 N이라면 1년 뒤의 박테리아 수는 1/2*N

Y년 후의 박테리아 수는 (1/2)^Y*N

박테리아의 소멸 시기: (1/2)^Y*N 의 값이 최초로 1보다 작아질 때 (1/2)^Y*N < 1

(1/2)^Y = 1/2^Y

    (1/2)^Y = N/2^Y < 1    양변에 2^Y를 곱해서

2^Y > N    양변에 로그를 취해서

Y > log2N

 

시간 복잡도 분석

O(logN)

 

*특정값을 계속 반으로 줄이는 동작을 하면 시간 복잡도는 O(logN)