[알고리즘 분석]8. Asymtotic Algorithm Analysis(점근 분석)

목차

1. Asymtotic Algorithm Analysis(점근 분석)

2. Prefix Averages(누적 평균 계산)으로  예시

 

1. Asymtotic Algorithm Analysis(점근 분석)

 알고리즘 수행 시간을 n에 따른 함수로 표현하지 않고 Big-Oh로 표현된다면, 이를 점근 분석이라고 합니다. 점근 분석을 실행하기 위해서는,

1. 알고리즘의 수도코드 작성

2. 각 줄마나 n에 따른 경우의 수 새기

3. 마지막으로 Big-Oh로 표현함 (즉, 총 합이 6n-1일 시 O(n)으로 표현 가능하다)

 

2. Prefix Averages(누적 평균 계산)으로 예시

 Prefix Averages(누적 평균 계산)알고리즘은 기존의 인원 수에서 계산된 평균에서, 추가 인원이 들어왔을 시 이에 따른 평균을 추가적으로 계산하는 알고리즘을 뜻합니다.

 

1) Prefix Averages Quadratic(2차)으로 구현

 위와 같은 방식은 새로운 인원이 들어올때마다, 전체 총합과 평균을 계산하는 것으로, 이중 for문을 사용하여 구현한 방식입니다. 우측의 operation을 보면, 이 알고리즘의 Big-Oh로 나타낸다면 O(1+2+3+ ... + n)으로, O(n^2)의 시간이 소모됩니다.

 

2) Prefix Averages Linear(선형)으로 구현

 위 알고리즘은 linear 방식으로 구현한 것으로, 앞선 첫 번째 방식과는 다르게 각 누적평균 마다 따로따로 한번씩 계산함으로서, O(n)으로 시간을 단축한 모습입니다.