문제

• 배열 X의 i번째 누적평균(prefix average)이란 X의 i번째에 이르기까지의 (i+1)개의 원소들의 평균
  (즉, $A[i] = (X[0]+X[1]+...+X[i])/(i+1)$)
• 배열 X의 누적평균(prefix average) 배열 A를 구하는 알고리즘을 의사코드로 작성하라

+응용) 경제, 통제 분야
: 오르내림 변동을 순화시킴으로써 대략적 추세를 얻어내기 위해 사용
: 부동산, 주식, 펀드 등에 활용

해결-누적평균(ver1)

2차시간(quadratic time)이 걸린다

Alg prefixAverage(X,n)
	input array X, A of n integers
    output array A of prefix averages of X
    
1. for i<-0 to n-1                {n}
		sum <- 0                  {n}
        for j<-0 to i             {1+2+...+n}
        	sum <- sum + X[j]     {1+2+...+n}
        A[i] <- sum / (i+1)       {n}
2. return                         {1}

Total $$O(n^2)$$

해결-누적평균(ver2)

중간 합을 보관함으로써
누적평균값들의 선형시간(linear time)에 구한다

Alg prefixAverage(X,n)
	input array X, A of n integers
    output array A of prefix averages of X

1. sum <- 0                      {1}
2. for i <- 0 to n-1             {n}
		sum <- sum + X[i]        {n}
        A[i] <- sum / (i+1)      {n}
3. return                        {1}
        

Total $$O(n)$$