[알고리즘] 알고리즘 효율 분석
1. 시간 복잡도란
- 알고리즘의 성능 지표
- 입력 크기에 대한 연산 횟수의 상한
- 낮으면 낮을 수록 좋음
2. 알고리즘 수행 시간 측정 방법
1) 절대 시간 측정 - 프로그램을 실행한 후 결과까지의 시간 측정
2) 시간 복잡도 측정 방법 - 알고리즘의 시작부터 결과까지의 연산 횟수
경우의 수는 대략 3가지 경우임
- 최선
- 보통
- 최악
(1) : 최악의 경우를 고려하라
(2) : 알고리즘 성능은 정확한 연산 횟수가 아닌 추이를 활용한다
3. 빅오 표기법
- 연산 횟수가 f(x)라고할때 함수의 최고차항을 남기고 O(…)와 같이 표기
- ex ) $2x^2+3x+5$ 라면 $O(x^2)$
- 왜 이렇게 쓰냐면 상한의 정확한 값이 필요한 것이 아니라 이정도가 될 것이다라는 추이를 보기 위함
| 시간 복잡도 | 최대 연산 횟수 |
|---|---|
| O(N!) | 10 |
| O(2^n) | 20~25 |
| O(N^3) | 200~300 |
| O(N^2) | 3000~5000 |
| O(NlogN) | 100만 |
| O(N) | 1000~2000만 |
| O(logN) | 10억 |
- 대략적인 데이터 개수를 확인하고 어떤 시간 복잡도를 사용해야하는구나 정도
- 어떤 문제를 풀던 시간 복잡도 계산 해보기
5. 시간 복잡도 계산해보기
(1) 문제 정의 → (2) 연산 횟수 측정 → (3) 시간 복잡도 분석
1) 별찍기 문제
숫자 N을 입력 받으면 N번째 줄까지 별을 1개부터 N개까지 늘려가면서 출력하기
연산 횟수 : 첫번째 줄은 1번 , 두번째줄은 2번 , 세번째줄은 3번 연산 …. N번째줄은 N번 연산함
결국 모든 줄에서 출력한 숫자의 개수를 합한 값이 총 연산 횟수임 ( 1+2+3+…+N)
합을 구하는 공식은
$N(N+1)/2$
$N^2$이 되니까 시간복잡도는 $O(N^2)$임
2) 박테리아 수명 문제
초기 박테리아 세포 개수가 n일 때 세포 개수가 이전 세포 개수의 반으로 줄어든다면 언제 박테리아가 모두 죽을지 계산하기
N이 16인 경우 5년이면 소멸함 → 8…4…2…1…0 (5번)
그렇다면 박테리아 개수가 N이면 1년뒤엔 1/2*N임
Y년 후라면 $(1/2)^Y*N$
박테리아의 소멸 시기는 $(1/2)^YN$ 의 값이 최초로 1보다 작아질 때 ( $(1/2)^YN$<1 인 경우)
- 양변을 N으로 나누면 $(1/2)^Y < (1/N)$
- 양변을 역수로 취하고 부등호를 바꾸면 $2^Y > N$
- 양변에 로그를 취하면 $Y> log2N$
- 따라서 O(logN)의 시간 복잡도를 가짐
