[알고리즘 뭐부터 해야돼?] 성능 분석

성능 분석

 

Language : JAVA 8

IDE : Eclipse

 

---

 

 

알고리즘 성능 분석에는 크게 공간 복잡도, 시간 복잡도로 나눠집니다.

이 둘에 대해 알아보고, 왜 성능 분석이 필요한지 생각해보겠습니다.

 

 

1) 복잡도를 계산하는 이유

어떤 알고리즘을 이용할지 결정하기 위해 작성할 코드의 연산 수&메모리를 고려하기 위함입니다.

 

 

2) 공간 복잡도

메모리 사용량을 측정을 통한 공간을 분석하는 방법으로 사용되는 메모리 공간의 총량을 계산합니다.

 

JAVA를 기준으로 int Type : 4 bytes , long Type : 8 bytes의 공간을 차지합니다.

256MB의 메모리를 가지고 있다고 가정해봤을 때, 256MB = 268,435,456 bytes 이므로
int Type 은 총 268,435,456 / 4 = 67,108,864 개 사용이 가능합니다.

 

 

3) 시간 복잡도

코드의 연산 횟수를 통한 속도를 분석하는 방법으로 연산 횟수를 계산합니다.

 

통상적으로 컴퓨터가 1초에 1억 번의 연산을 할 수 있다고 가정한다면, 

시간 복잡도를 계산해서 알고리즘의 수행 시간을 계산 or 예측할 수 있습니다.

 

아래 반복문을 확인해보면, 배열의 길이만큼 수행되므로 연산 횟수는 array.length인 10번입니다.

int[] array = new int[10];
for(int i=0; i < array.length; i++) {
	system.out.println(array[i]);
}

 

 

4) 시간 복잡도가 공간 복잡도보다 중요한 이유

시간도 적게 걸리고 자원의 사용도 적어야 하는 것이 좋은 알고리즘 풀이의 목표입니다.

 

빅데이터 분석과 같이 큰 데이터를 사용하는 경우라면 공간 복잡도 또한 중요하게 생각해야 합니다.

 

하지만, 일반적으로 시간 복잡도가 알고리즘 성능에 더 많은 영향을 미치기 때문에,

성능 분석을 한다고 하면 대부분 시간 복잡도에 관한 분석이라 생각하시면 됩니다.

 

 

6) 시간 복잡도 표기법

최악의 경우의 수인 최댓값을 기준으로 시간 복잡도를 계산합니다.

 

① 빅-오(Big-Oh, O(N)) : Worst case의 연산 횟수 ② 빅-오메가(Big-Omega 옴 표시(N)) : Best Case의 연산 횟수 ③ 빅-세타(Big-theta, 세타 표시(N)) : Average Case의 연산 횟수

일반적인 시간 복잡도 표기법으로는 빅-오 O(N) 표기법을 사용합니다.

연산 횟수가 항상 일정하지 않기 때문에, 최솟값보다는 가장 최악일 때인 최댓값을 사용하는 것이 좋기 때문입니다.

 

 

7) 시간 복잡도 예시

최악의 경우의 수인 최댓값을 기준으로 시간 복잡도를 계산합니다.

 

빅-오 O(N) 표기법에 따라 3N^2으로 표기되고, 보통 상수는 제외하고 O(N^2) 로 표시합니다. 

// O(N^2)
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		num[i][j] =sc.nextInt();
	}
}

// O(N^2)
int ans[] = new int[N*N+1];
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {	
		num[i][j] +=2;
		if (num[i][j] == M) ans[idx++] = i;
	}
}

// O(N^2) -> 위에 코드의 idx 갯수의 영향
for (int i = 0; i < idx; i++) {
	result += ans[i];
}

 

 

8) 시간 복잡도 종류

 

· 상수형 O(1)

길이가 N인 배열에서 M번쨰 배열 값을 출력 (M <= N)

 

· 선형 O(N)

정렬되지 않은 길이가 N인 배열에서 가장 작은 수를 탐색

for(int i=0; i < length; i++)

 

· 2 차형 O($N^2$) 

버블 정렬, 삽입 정렬, 퀵 정렬의 Worst Case

for(int i=0; i < length; i++) {
	for(int j=0; j < length; j++) {
	}
}

 

· 3 차형 O($N^3$) 

플로이드-워셜 알고리즘

for(int i=0; i < length; i++) {
	for(int j=0; j < length; j++) {
		for(int k=0; k < length; k++) {
		}	
	}
}

 

· 로그형 O($log 2 N$)

N개의 정렬된 수열에서 이분 탐색을 통해 특정 숫자를 탐색, 우선순위 큐 또는 힙에서의 원소 삽입, 삭제 연산

for(int i=0; i < length; i*=2)

 

· 팩토리얼형 O($N!$)

1부터 N까지의 숫자를 나열할 수 있는 모든 방법을 출력하는 함수

 

· 지수형 O($2^N$) 

번호가 매겨진 N개의 동전을 던졌을 때 나올 수 있는 경우를 출력하는 하수

 

· 선형 로그형 O($Nlog2 N$) 

힙 정렬, 병합 정렬, 퀵 정렬의 Average Case

 

O (1) > O ($log 2 N$) > O ($N$) > O ($Nlog2 N$) > O ($N^2$) > O ($N^3$) > O ($2N$) > O ($N!$)