예제 : 수열의 빠른 합

public class FastSum {
    public static void main(String[] args) {
        System.out.println(fastSum(10));
    }
    
    public static int fastSum(int n) {
        if(n == 1) {
            return 1;
        }
        if(n%2 == 1) return fastSum(n-1) + n;
        return 2*fastSum(n/2)+n/2*n/2;
    }
}

 

1 + 2 + 3 + 4 + 5 + ... + n 을 반으로 나누어서 계산해 보자

 

1 + 2 + 3 + ... n/2 + (n/2+2) + (n/2+3) + (n/2+4) + (n/2+n/2)

 

= f(n/2) + n/2*n/2 +f(n/2)

=> 2f(n/2) + n/2*n/2 가 된다.

 

n은 짝수일때 성립한다.

 

위의 코드를 보면 n이 홀수일 때는 f(n-1) + n을 하여 홀수일 때를 처리해 준다.

 

1부터 n 까지 더해주는 반복문은 무조건 n번 반복해서 수를 더해준다.

 

하지만 위의 코드를 보면 n이 짝수가 될때마다 n을 2로 나누어서 계산하기 때문에 훨씬더 빠르게 계산되는 것을 알 수 있다.