[알고리즘 학습] 프로그램의 성능 분석

프로그램의 성능을 분석할 필요가 있을까요?

네, 있습니다. 왜 일까요.

입력 데이터의 크기에 따라서 1. 실행속도와 2. 메모리 사용량 이 어떻게 변하는지 예측이 필요합니다.

 

프로그램의 성능 분석이란

입력 데이터의 크기에 따라서 어떤 성능을 보이는지 예측하고 원하는 성능에 미치지 못하는 경우 그 이유를 찾아보는 것입니다.

 

왜 필요할까요? 우리의 컴퓨터는 자원이 제한적이고, 우리가 앞으로 다뤄야 할 데이터들은 한없이 많아지고 있기 때문입니다.

비즈니스적 측면에서도 유용합니다.

' 내 프로그램을 실행하면 왜 느릴까?, 내 프로그램을 사용하면 왜 메모리가 부족해질까? '

 

프로그램의 성능 표현 방법
   ~f(N): 입력 데이터 크기가 N일 때, 프로그램의 성능이 대략적으로  f(N)에 비례함
   예: “~Nlog(N)”은 프로그램의 성능이 대략적으로 Nlog(N)에 비례함 의미

 

O, Ω, Θ 등을 사용한 표현 방식은 그 의미가 포괄적이라서

(예: O(N)인 알고리즘은동시에 O(NlogN), O(N2), O(N3)이기도 함) 

위와 같은 더 간단하고 명확한 표현하나로 통합해 사용하게 되었습니다.

 

 

변수값 증가

i = N번, j는 N-1 n-2 n-3 ... 1 => N(N+1)/2 - N , count는 0~N(N+1)/2 항상이니까. 

즉 변수값 증가는, N(N+1)/2~N(N+1).

 

알고리즘, 즉 프로그램 전체의 부분을 모두 계산하는 것은 불필요하다, 너무 많은 시간이 소요된다.

그래서 적당히 그룹별로 나눈다. 비슷한 수치로 반복되는 부분들이 많아서 그룹화 할 수 있다.

이때 여러 그룹이 나올텐데, 그 그룹들 중 가장 수치가 높은 그룹을 기준으로 삼고, 그 그룹안에서 계산이 쉬운 수행과정을 최종 기준으로 삼고 계산하면 된다. 왜냐하면, N이 커질수록 각 그룹간의 계산 격차가 커져서 다른 그룹의 수행 빈도를 압도하기 때문이다.

 

가장 많이 수행하는 그룹중 하나의 빈도를 셌다면, 그 값을 간소화 합니다.

1. 여러 항으로 구성되어 있다면 가장 큰(차수가 가장 큰) 항만 남깁니다.

2. 그리고 변수 부분을 제거합니다. (. 예를 들어 가장 큰 항이 2N3이라면 상수 2를 제거하고 ~N3으로 표현합니다. ) 

 

 

(더 자세한 비교를 위해 꼭 필요한 경우에는 단순화 단계 일부를 생략하고 상수나 low-order term을 보여주기도
합니다)

 

 

지금까지 프로그램의 추상적 모델(수학적 모델)을 만드는 방법에 대해
알아보았습니다. 정리하면 3단계 정도의 단순화를 거칩니다. (1) 프로그램이
수행하는 작업 중 가장 많은 빈도로 수행되는(가장 비중이 큰) 작업을 선정해 수행
횟수를 세고, (2) 수행 횟수에서 가장 큰 항만 남긴 후, (3) 상수 부분을 제거합니다.

 

 

 

표의 마지막 열 ‘T(2N)/T(N)’는 ‘입력의 크기가 2배가 될 때 수행 시간이 몇 배
증가하는가’를 나타냅니다. T(2N)은 입력 크기가 2N일 때의 수행 시간을 나타내며, T(N)은 입력 크기가 N일 때의 수행 시간을 나타내기 때문입니다.

 

이 중 log(N)의 T(2N)/T(N)은 ~1 입니다. 1(상수시간)의 T(2N)/T(N)인 1과 유사하지만 다르다는 뜻이죠.

N의 T(2N)/T(N)은 2입니다. 즉 표본인 N이 두배가 되는 경우에, log(N)의 성능은 상수 수학적 모델인 1인 성능에 훨씬 가깝다는 것이고, 매우 우수하다는 뜻입니다.

 

이는, ~N인 프로그램을 ~log(N)으로 개선한다면 큰 속도 차이를 느낄 수 있지만 ~log(N)을 ~1로 개선했다면 상대적으로
성능 개선 폭이 적다는 것을 의미합니다. 마찬가지로 N log(N)은 N2보다는 N과 훨씬 더 가까우며, 따라서 많은 경우 ~N인 프로그램과 유사한 성능을 보입니다.