-
프로그램의 성능 분석
입력 데이터의 크기에 따라 프로그램 실행 속도 및 메모리 사용량이 어떻게 변하는지 예측
원하는 성능에 미치지 못하는 경우, 원인 파악하여 수정 -
프로그램 성능 분석을 시작하게 된 이유
"내 프로그램이 실제 사용되었을 때, 큰 입력 데이터와 다수의 동시 사용자를 잘 감당할 수 있을까"에 대한 궁금증 해결
=> O(N), O(N^2)과 같은 형식으로 성능을 표현하는 체계적인 방법이 개발됨. -
프로그램 성능 표현 방법
~ : 프로그램의 성능이 대략적으로 ~ 오른쪽 수 에 비례한다는 의미 -
매우 정확한 성능 계산보다는 대략적으로 서로 다른 알고리즘 간의 차이를 큰 틀에서 빠르게 파악하는데 초점 (O, Ω, Θ)
-
프로그램의 성능 분석 과정 개요
프로그램에 대한 추상적인 모델(수학적 모델) 만들어 성능 예측
입력 데이터 크기 바꿔가며 성능 측정해 예측 맞는지 검증
예측이 맞지 않아 모델 수정할 필요 있따면 위 과정 반복 -
프로그램에 대한 추상적 모델 만드는 과정(1)
프로그램이 수행하는 여러 작업과 수행 빈도를 입력 데이터 크기 N을 사용해 나타내기
#a, N: 입력값과 그 길이
int count = 0;
for (i = 0; i < N; i++)
if (a[i] == 0)
count++;변수 선언(count, i) : 2번
변수에 초기값 저장(count=0, i=0) : 2번
< 비교(i=0~N) : N+1번
== 비교(i=0~N-1) : N번
배열 접근(i=0~N-1) : N번
변수 값 증가(i++: N번 & count++: 0~N번) : N~2N번
- 프로그램에 대한 추상적 모델 만드는 과정(2)
#a[], N: 입력갓과 그 길이
int count = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < n; j++)
if(a[i] + a[j] == 0)
count++;변수 선언(count: 1번, i: 1번, j: N번) : N+2번
변수에 초기값 저장(count: 1번, i: 1번, j: N번) : N+2번
< 비교(i: 0~N: N+1번, j: N(N+1)/2번) : (N+1)(N+2)/2번
== 비교(NC2번) : N(N-1)/2번
배열 접근 : N(N-1)번
변수 값 증가(i++: N번, j++: 0~N(N-1)/2번, count++: 0~N(N-1)/2번) : N~N^2번
위와 같이 프로그램이 복잡해 질수록 정확한 계산 어려움.
위 작업에서 처음 2개 작업은 ~N회, 나머지 4개 작업은 ~N^2회 발생함.
따라서 가장 많이 수행되는 작업 중 하나의 횟수만 세면 됨.
-
프로그램에 대한 추상적 모델 만드는 과정 (3)
빈도수가 여러 항으로 구성되어 있다면, 이 중 가장 큰 항만 남기고 나머지 작은 항은 제거
ex) 가장 많이 수행하는 작업이 2N^3 + 4N^2회 수행된다면, 2N^3만 남김. -
프로그램에 대한 추상적 모델 만드는 과정 (4)
가장 큰 항에서 상수 부분 제거
ex) 가장 큰 항이 2N^3라면, ~N^3으로 표현
Q. 프로그램의 수행 속도를 나타내는 수학적 모델을 만들고 단순화하였다. 단순화한 결과로 올바른 것은?
1. ~N^3/6 - 20N + 16
2. ~(N+1)(N+2)/2
3. ~2N + log(N)
4. ~N log(N)
5. ~3N^2
A. 4번 (~N log(N))
Q. 다음 프로그램의 수행 속도를 나타내는 수학적 모델로 올바른 것은?
int count = 0; for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) for (int k = j+1; j < N; k++) if (a[i] + a[j] + a[k] == 0) count++;A. a[i]+a[j]+a[k] => NC3 => N(N-1)(N-2)/6 => ~N^3
Q. 크기 N인 정수 리스트 a[ ]가 입력으로 주어진다. 이 중 서로 다른 3개 원소의 합이 0이 되는 경우를 모두 찾고 싶다. Brute-force 알고리즘을 사용해 서로 다른 3개 원소 모두를 차례로 검사하는 경우, 수행 시간은 무엇인가? 예를 들어, a = {1, -1, 0, 2}가 주어진다면, {1, -1, 0}, {1, -1, 2}, {1, 0, 2}, {-1, 0, 2}를 차례로 검사해 이 중 합이 0인 경우를 찾는다.
A. NC3 = N(N-1)(N-2)/6 => ~N^3
