알고리즘의 시간복잡도란
알고리즘의 속도는 코드에 반복문이 수행되는 횟수로 측정한다.
이때 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현한다.
선형 시간 알고리즘이란
코드의 수행시간이 입력의 크기에 정비례하는 코드로 대게 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다.(입력 전체를 한번은 확인해야 한다.)
이동평균을 이용하여 선형시간 알고리즘을 이해해 보았다.
이동평균이란
하루에 마시는 믹스커피 개수를 예로 들어 보면
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
.
.
.
을 모두 계산하여 나타내는 것이다.
무식하게 코드를 짜면
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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;
}
|
cs |
위와 같이 배열에 있는 값들을 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으로 나누어 주면 된다.
이 규칙으로 코드를 작성해 보면
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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;
}
|
cs |
(EX)
첫번째 반복문에서
- 1+2의 값이 A[0]에 저장된다.
두번째 반복문에서
- 1+2의 값에 3을 더해주고 그것을 3으로 나누어 배열에 저장한다.
- 그다음 1+2+3에서 1을 빼고 반복문을 나간다 partialSum에는 2+3의 값이 저장되어 있다.
시간복잡도를 계산해 보면
M-1번실행
N-M+1번실행 으로
총 시간 복잡도는 M-1+(N-M+1) = N이 된다.
같은 동작을 하지만 시간복잡도는 줄어들어 더 빠른 코드가 되었다.
- 알고리즘 문제해결전략(인사이트)을 공부하며 정리한 내용 입니다.
'알고리즘 > Algorithm' 카테고리의 다른 글
Recursion의 응용 - 미로찾기 (0) | 2021.01.19 |
---|---|
2진검색 알고리즘 (0) | 2021.01.19 |
Recursion(순환)-3 (0) | 2021.01.19 |
Recursion(순환)-2 (0) | 2020.07.05 |
Recursion(순환)-1 (0) | 2020.06.27 |