1. 알고리즘 성능 분석 및 시간 복잡도

알고리즘의 성능 분석 방법

 

우리의 목표는 “알고리즘이 잘 작동 + 좋은 성능 보장” 이 되기를 원한다. -> 자료구조와 알고리즘을 분석 및 평가 를 통해 확인

 

1) 어떤 알고리즘이 어떠한 상황에서 더 빠르고? 또 느리나? - 속도 -> 시간 복잡도

2) 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰나 – 메모리 -> 공간 복잡도

 

하지만 우리의 주목적은? “시간 복잡도”

 

그러면 어떻게 속도를 평가할까?

1) 연산의 횟수를 센다.

2) 그리고 처리해야 할 데이터의 수 n에 대한 연산 횟수의 함수 T(n)을 구성한다.

-> 식을 구성하면, 데이터 수의 증가에 따른 연산 횟수의 변화 정도를 판단할 수 있다. 따라서 그래프로 표현이 가능하다.

 

이를 통해, 데이터가 적으면 B 알고리즘이 빠르고, 데이터가 많으면 A 알고리즘이 빠르다. 는 것을 확인 할 수 있다.

 

순차 탐색(Linear Search) 알고리즘과 연산 횟수의 함수 T(n)

	
static void linearSearch(int[] arr, int len, int target) {
	for(int I = 0; I < len; I++) {
		if(arr[i] == target) return i;
	}
	return –1;
}
 	
 

-> 다음과 같은 순차 탐색 함수의 T(n)을 구해보자.

여기서 시간 복잡도는 ‘데이터 수 n에 대한 연산 횟수의 함수 T(n)’을 구하면 된다. 제일 먼저 핵심이 되는 연산이 무엇인지 확인하자!

 

연산의 종류 :           ➀ <             ➁ ++            ➂ ==

-> “==”(비교연산)를 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

-> “==”는 “<”와 “++”의 횟수에 영향을 준다.

 

그러면 “==”(비교연산) 횟수를 계산해보자.

1) 찾고자 하는 target이 ‘맨 앞’에 있을 때 (Best-case)

-> 어떠한 알고리즘이더라도 최선의 경우는 대부분 만족하기 때문에, 관심 대상이 아니다.

2) 찾고자 하는 targetdl ‘맨 뒤’에 있을 때 (Worst-case)

-> 아까 봤던 그래프를 예로 다시 들자.

-> 데이터의 수가 많아지면 ‘최악의 경우’에 수행하게 되는 연산의 횟수는 알고리즘 별로 큰 차이가 있다.

-> 따라서, 최악의 경우가 핵심이 된다.

 

여기서 의문? 최악도 최선의 경우가 아닌, 평균적인 경우를 따져야 하는 것 아닌가? 이게 더 현실적인 것 같다.

-> 실제로 평균적인 경우는 시간 복잡도를 평가하는 정보로 의미를 지닌다. 하지만 평균적인 시간 복잡도를 구하기는 쉽지가 않다. 

    또한, ‘무엇이 평균적인 상황인가?’라는 질문에 대답하기 어렵다.

 

그러면 실제로 순차탐색 알고리즘의 최악의 경우와 평균의 경우를 구해보자.

1) 최악의 경우

- 데이터의 수가 n개 일 때, 최악의 경우에 해당하는 연산(비교연산)의 횟수는 n

2) 평균의 경우 (가정이 필요하다)

가정 1) 탐색 대상이 배열에 존재하지 않을 확률을 50%라 가정

가정 2) 배열의 첫 요소부터, 마지막 요소까지 탐색 대상이 존재할 확률은 동일하다.

경우 1. 탐색 대상이 존재하지 않을 경우	경우 2. 탐색 대상이 존재할 경우
연산 횟수 = n	연산 횟수 = 대략 n/2
	n이 5일 때, target이 첫 번째 있으면 연산 횟수는 1, target이 마지막에 있으면 연산 횟수는 5 이므로, 평균은 3이다. (하지만, 5/2 = 2.xxxx 이므로 대략이라 표현)

따라서      이 된다.

 

이를 통해,

 1. 최악의 경우보다 계산하는 것이 쉽지 않다.

 2. 신뢰도가 낮다. -> 앞의 2개의 가정에 대한 근거가 부족하기 때문이다.

를 알 수 있다.

 

이진탐색(Binary Search) 알고리즘과 연산 횟수의 함수 T(n)

	
static void binarySearch(int[] arr. int first. int last) {
	while(first <= last) {
		mid = (first + last) / 2;
		if(target == arr[mid]) return mid;
		else { ... }
	}
}
 	
 

-> 연산 횟수를 대표하는 것은? “==”(비교 연산)

-> 이진 탐색의 경우 다음과 같이 진행이 된다.

 

처음의 데이터의 수가 n개일 때, 탐색 과정에서 1회의 비교 연산이 진행

이후 데이터의 수가 n/2일 때, 탐색 과정에서 1회의 비교 연산이 진행

이후 데이터의 수가 n/4일 때, 탐색 과정에서 1회의 비교 연산이 진행

...

이후 데이터의 수가 1일 때, 탐색 과정에서 1회의 비교 연산이 진행

 

즉, n = 8인 경우, 2로 나눈 횟수가 3번, 따라서 비교 연산의 횟수 또한, 3회이다.

 

이를 일반화하면

1) n이 1이 될 때까지, 2로 나눈 횟수를 k회라 가정하면, 비교연산 k회 진행

2) 데이터가 1개 남았을 때, 마지막 비교 연산 1회 진행

따라서, 이 된다.

하지만 ‘+1’은 필요가 없다. 이유는 아래 그래프와 같이 n이 증가할수록 T(n)도 끊임없이 증가하기 때문에, ‘+1’은 무시할 수 있다.

 

※빅 오 표기법 

 -> T(n)에서 가장 영향력 있는 부분은 어디인지만 파악하면 된다.

- 시간 복잡도를 이용하면 작성한 코드가 시간이 얼마나 걸리는지 예상할 수 있다.

- 빅오 노테이션의 경우, 최악의 경우에 시간이 얼마나 걸리는지 알 수 있다.

- 시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초 정도이다. (확실한 값은 아니다.)

  1) 순차 탐색 알고리즘 T(n) = n ... 빅오표기법 O(n)

  2) 이진 탐색 알고리즘 ... 빅오표기법 O()

 

- 항상은 아니지만, 대부분의 경우에 해당

O(1)	단순 계산 (a+b와 같은 연산, 배열에 접근하는 연산)
O()	n개를 절반으로 계속해서 나눔
O(n)	1중 for문
O()	-
O(n^2)	2중 for문
O(n^3)	3중 for문
O(2^n)	크기가 n인 집합의 부분집합
O(n!)	크기가 n인 순열

- 성능(수행시간, 연산횟수) 비교

O(1) < O() < O(n) < O() < O(n^2) < O(n^3) < O(2^n) < O(n!)