선형 시간 알고리즘

알고리즘의 시간복잡도란

알고리즘의 속도는 코드에 반복문이 수행되는 횟수로 측정한다.

이때 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현한다.

 

선형 시간 알고리즘이란 

코드의 수행시간이 입력의 크기에 정비례하는 코드로 대게 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다.(입력 전체를 한번은 확인해야 한다.)

 

이동평균을 이용하여 선형시간 알고리즘을 이해해 보았다.

이동평균이란

 

하루에 마시는 믹스커피 개수를 예로 들어 보면

1일	2일	3일	4일	5일	6일	7일	8일
3개	4개	5개	3개	4개	3개	3개	4개

M-이동평균에서 M을 3이라고 한다면

 

3일에 : (1일+2일+3일)/3 

4일에 : (2일+3일+4일)/3

5일에 : (3일+4일+5일)/3

.

.

.

을 모두 계산하여 나타내는 것이다.

 

무식하게 코드를 짜면 

 public static List<Double> getMovingAverage(int[] A , int M){
 
        List<Double> result = new ArrayList<Double>();
        int N = A.length;
        for(int i = M-1; i < N; i++){
            double partialSum = 0;
            for(int j = 0 ; j < M; j++){
                partialSum += A[i-j];
               }
            result.add(partialSum/M);
        }
        return result;
    }

위와 같이 배열에 있는 값들을 M번째 부터 M개씩 더하고 M으로 나누는 것을 반복하도록 할 수 있다.

 

이것은 시간복잡도 관점에서 본다면 

 

j를 사용하는 배열은 항상 M번 반복된다.

i를 사용하는 배열은 N-M+1번 반복된다.

 

전체 반복문은 M(N-M+1) = MN-M^2+M번 반복된다.

 

하지만 위의 규칙을 잘 보면

M-1번째 이동평균을 구할때와 M번째 이동평균을 구할때 중복이 발생하는 것을 알 수 있다.

 

3일에 : (1일+2일+3일)/3

4일에 : (2일+3일+4일)/3

5일에 : (3일+4일+5일)/3

 

만약 5일의 이동평균을 구한다면 4일 이동평균에서 첫번째 값을 빼고 5일의 값을 더해서 3으로 나누어 주면 된다.

이 규칙으로 코드를 작성해 보면 

public static List<Double> getMovingAverage2(int[] A, int M){
 
        List<Double> result = new ArrayList<Double>();
        int N = A.length;
        double partialSum = 0;
 
        for(int i = 0; i< M-1; i++){
            partialSum += A[i];
        }
        for(int i = M-1; i<N; i++){
            partialSum += A[i];
            result.add(partialSum/M);
            partialSum -= A[i-M+1];
        }
        return result;
    }

시간복잡도를 계산해 보면 

 

M-1번실행

N-M+1번실행 으로 

총 시간 복잡도는 M-1+(N-M+1) = N이 된다.

 

 

같은 동작을 하지만 시간복잡도는 줄어들어 더 빠른 코드가 되었다.

 

 

 

 

 

 

 

 

• 알고리즘 문제해결전략(인사이트)을 공부하며 정리한 내용 입니다.