#2(시간 복잡도 & 정렬)

알고리즘 이란??

문제를 해결하기 위한 절차

 

에를들어 서울 광화문에서 제주도로 가는 방법을 생각해봅니다.

1. 먼저 자신이 광화문 어디에 있는지 위치 파악을 합니다.

2. 위치파악을 끝냈으면 김포공항으로 갈 수 있는 가장 가까운 버스 정류장을 검색하고 갑니다.

3. 버스를 타고 공항에 도착하면 수속 절차를 끝내고 비행기를 타고 제주도로 갑니다.

 결국 광화문에서 제주도로 가능 방법의 최종 목표는 '비행기 타기' 입니다.

즉, 우리는 문제가 주어졌을때, 최종목표를 파악하는 것이 중요합니다.

이를 위해 우리는 항상 올바른 답을 내야하고 유한한 시간 안에 종료를 해야합니다.

 

좋은 알고리즘 이란??

이해할 수 있어야 하며, 간결해야 합니다.

주어진 자원의 한계를 생각해야 합니다.

알고리즘을 수행하는 데에 걸리는 시간을 생각해야 합니다. 

여기서 우리는 평범하게 좋은 알고리즘이란 가장 빠른 알고리즘 이라고 합니다.

왼쪽 알고리즘과 오른쪽 알고리즘을 비교해 봅시다.

둘다 1부터 n까지의 합을 더하는 알고리즘입니다. 

왼쪽 알고리즘은 i<=n비교연산,  i++연산, result +=i 연산 해서 n번 반복하므로 약 3n의 연산을 하게됩니다.

반면에 오른쪽 알고리즘은 가운데 for문 3n의 연산에서 또 다시 n번의 연산을 하게 됩니다.

그래서 총 계산 해보면 1.5n^2+4.5n+2의 연산을 갖게 됩니다.

3n+2와 1.5n^2+4.5n+2중 누가 더 빠른 알고리즘일까요??

n에 자연수 아무나 넣어도 1.5n^2+4.5n+2가 더 크기 때문에 시간이 더 오래걸립니다.

즉, 오른쪽 3n+2가 더 작으므로 더 빠릅니다. 

그렇다면 0.1n^2 + 3n + 7 과 1000n +7654중 누가 더 빠를까요?

n이 작은 수라면 0.1n^2 + 3n + 7이 더 작기 때문에 더 빠를것 같습니다.

하지만 n이 비교적 큰 수 가 된다면 0.1n^2 + 3n + 7이 커져서 1000n +7654이 나중에는 더 빨라집니다.

여기서 중요한 사실은 두식의 상수와 계수들을 뺀 최고차항을 고려해도 같은 결과를 얻는다는 사실입니다.

즉, 0.1n^2 + 3n + 7 = n^2이 되고 1000n +7654 = n 이 됩니다.

n^2 vs n 누가 봐도 n이 작으므로 1000n +7654이 더 빠른 알고리즘이란 것을 알 수 있습니다.

빅오표기법

0.1n^2 + 3n + 7를 빅오표기법으로 나타내면 O(N^2) 이 되고 1000n +7654는 O(N)이 됩니다.

 f(n) = O(g(n)) 이라는 것은, 적당히 큰 x에 대해서 대충 f(x)보다 g(x)가 크다는 의미입니다.

이는 다시 말해서 어떤 상수 c가 있을때, f(n) ≤ cg(n) 이 성립하면 f(n) = O(g(n))입니다.

여기서 조건은

1. (적당히 큰 수에 대해서)f(n)의 증가량이 g(n)의 증가량을 넘지 않는다.

2. 대략적인 f(n)이 상한을 알 수 있다.

3. 서로 다른 알고리즘의 시간 복잡도를 쉽게 비교할 수 있다.

예를들어 f(n)을 1000n으로 두고 g(n)을 n으로 설정하고 c의 값을 1000이라고 한다면 

f(n)≤1000g(n) 이므로 f(n)은 빅오표기법으로  O(g(n))을 사용할 수 있습니다.

따라서 1000n =O(n)입니다.

정렬

정렬 알고리즘을 알아보겠습니다.

---

버블정렬

1. 다음을 n-1번 반복한다.

2. 앞에서 부터 인접한 두 개를 비교하면서 올바른 순서가 되도록 한다.

3. 현재 i번째 반복을 수행하는 경우 끝에서 i번째 원소를 제외하고 비교해도 된다.(i는 0부터 시작, 0번째 반복은 마지막 원소까지 봐준다.)

코드를 살펴보겠습니다. (c언어로 작성했습니다.)

void BubbleSort(int arr[], int n) {
	for (int i = 0; i < n-1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

 

앞에서 부터 두수를 비교해 오른쪽 수가 왼쪽에 있는 수보다 작으면 둘이 스왑해주면 됩니다.

결국 반복 사이클이 1번을 돌게 되면 배열에 있는 가장 큰 수는 맨 오른쪽으로 이동하게 됩니다.

이중 for문을 사용중이므로 시간복잡도는 O(N^2)을 갖게 됩니다.

---

삽입 정렬

1. 다음을 n번 반복한다.

2. 현재 i번째 반복을 수행하는 경우 i번째 원소를 앞의 원소들과 (역순으로) 차례차례 비교한다.

3. 처음으로 등장하는 i번째 원소보다 크지 않은 원소의 뒤에 i번째 원소를 위치시킨다.

코드를 살펴 보겠습니다. (c언어로 작성했습니다.)

void InsertionSort(int arr[], int n) {
	int key;
	int i, j;
	for (i = 1; i < n; i++) {
		key = arr[i];
		for (j = i - 1; j >= 0; j--) {
			if (arr[j] > key)
				arr[j + 1] = arr[j];
			else
				break;
		}
		arr[j + 1] = key;
	}
}

key 값은 비교 기준이 되는 값입니다. key값의 왼쪽에는 항상 key보다 작아야하고, key값의 오른쪽은 항상 key보다

커야 합니다. 

삽입정렬도 이중 for문을 사용 중이므로 O(N^2)의 시간복잡도를 가집니다.

삽입 정렬과 버블 정렬은 둘다 시간복잡도가 O(N^2)이므로 알고리즘의 효율성은 비슷해 보이지만

때로는 삽입정렬이 버블정렬보다 더 좋을때가 있습니다.

예를 들어 배열에 2, 3, 4, 5, 6, 1 이렇게 있다고 가정해 봅시다.

처음 key 값이 3이고 오른쪽, 왼쪽 둘다 만족합니다. 그래서 움직일 필요가 없습니다.

또 다음 key 값도 4고 오른쪽, 왼쪽 둘다 만족합니다. 이렇게 계속 움직이다가

key값이 6이되면 처음으로 6오른쪽에 1이 있으므로 알고리즘이 실행됩니다.

이럴때는 시간복잡도가 O(N)으로 줄어듭니다.

따라서 정렬알고리즘중에 O(N^2)의 시간복잡도를 가지는 정렬중 삽입정렬이 최적화에 많이 쓰입니다.

그러므로 정렬이 대충 어느정도 되어있다면 삽입정렬을 하는게 효율적입니다.

---

병합정렬(merge sort)

1.정렬해야 할 배열의 크기가 1이라면 종료한다.

2. 그렇지 않으면 배열을 같은 크기로 나눈다.

3. 나눈 각각의 배열에서 병합 정렬을 수행한다.(재귀적 정의 가 들어갑니다)

4. 정렬한 두 개 배열 각각의 첫 번째 원소부터 차례로 비교하여 전체 배열을 정렬한다.

코드를 살펴보겠습니다.(c언어로 작성했습니다.)

void merge_sort(int arr[], int l, int r) {//다 반으로 나누고 나중에 정렬
	if (l < r) {
		int m = (l + r) / 2;
		merge_sort(arr, l, m);
		merge_sort(arr, m + 1, r);
		merge(arr, l, m, r);
	}
}

 

먼저 나누는 부분입니다. arr배열의 맨 처음 인덱스 번호를 int l, 마지막 인덱스 번호를 int r로 설정해둡니다.

그 다음 if(l < r) 만약 l<r 이 성립한다면, 계속 수행해줍니다. if문을 통과하지 못하면 l≥r 이므로 성립하지 않습니다.

그 다음 배열의 중간인덱스 번호값을 구해줍니다. 간단히 (l+r) /2 를 이용하여 먼저 배열의 절반을 나눌 것입니다.

그 다음 이제 배열의 절반인덱스 번호(m)을 기준으로 merge_sort(arr, l ,m)은 오른쪽, merge_sort(arr, m+1, r)은 왼쪽

으로 나누어 재귀적으로 수행합니다. 오른쪽으로 계속계속 재귀적으로 수행하면 l이 r과 같아지는 구간이 옵니다.

그 구간이 바로 배열을 다 나누어서 인덱스번호가 1개 밖에 안남았다는 sign입니다.

이제 다 나누었던 배열을 합칩니다.

void merge(int arr[], int l, int m, int r) {
	int idx1, idx2, idx3;
	idx1 = idx3 = l;
	idx2 = m + 1;

	while (idx1 <= m && idx2 <= r) {
		if (arr[idx1] <= arr[idx2])
			tmp[idx3++] = arr[idx1++];
		else
			tmp[idx3++] = arr[idx2++];
	}
	if (idx1 > m) {
		for (int i = idx2; i <= r; i++)
			tmp[idx3++] = arr[i];
	}
	else {
		for (int i = idx1; i <= m; i++) {
			tmp[idx3++] = arr[i];
		}
	}

	for (int i = l; i <= r; i++) { //정렬된 tmp배열을 다시 arr배열로 옮기기
		arr[i] = tmp[i];
	}
}

merge부분 입니다. 

먼저 merge함수는 매개변수(parameter)로 배열과 배열의 시작(l), 배열의 중간(m), 배열의 끝(r) 총 4가지를 받습니다.

그 다음 idx1은 오른쪽배열의 시작(l) 값을 가집니다. idx2는 m+1의 값을 가지므로 왼쪽배열의 시작점의 값을 가집니다.

idx3은 오른쪽 배열과 왼쪽 배열을 정렬한 새로운 배열의 맨처음 인덱스번호(l)를 가집니다.

while문으로 들어가면 idx1 ≤ m 그리고 idx2 ≤ r 이면 계속 반복합니다. 

그 다음 idx1 과 idx2와 비교해서 둘중 작은값이 tmp배열의 idx3의 자리로 들어갑니다.

둘중 하나가 idx3의 자리로 들어가면 idx3++을 해주어 다음 인덱스에 들어가게 설정을 해줍니다.

이는 idx1 과 idx2도 마찬가지로 둘이 서로 비교해서 둘중 작은값 인덱스를 ++해주어 다음 인덱스와 비교하게하기 위함입니다.

while 문이 끝나면 오른쪽 배열이나 왼쪽 배열이 둘중 하나가 m값에 도달했거나 r값에 도달했을 것입니다.

그러면 도달한 배열을 제외한 나머지 배열을 연속으로 tmp배열에 넣어줍니다. 

이미 tmp배열을 정렬되게 값이 들어갔고, 오른쪽배열도 , 왼쪽배열도 이미 정렬되어 있는 상태이기 때문입니다.

마지막으로 모두 정렬된 tmp배열을 arr배열로 옮겨 주면 끝이 나게 됩니다.

 

병합정렬의 시간 복잡도는 다음 과 같습니다.

예를들어 배열의 크기가 8이라고 할때,

우리는 배열의 크기가 1이 될때까지      merge_sort함수를 총 7번 수행하게 됩니다.

즉 n=8일때, n-1=7번하게 됩니다.

그렇다면 몇단계를 거쳐야 배열이 1개가될까요??

첫번째 단계는 8/2=4 가 됩니다.

두번째 단계는 4/2=2 가 됩니다.

세번째 단계는 2/2=1 이 됩니다.

즉, 총 3번의 단계를 거쳐야 배열의 갯수가 1이

됩니다.

이를 반대로 생각하면 배열의 크기가 1일때, 몇단계를 거쳐야 8이 될까를 생각해보면

1 × 2^3 = 8 이됩니다. 즉 3단계를 거쳐야 배열의 크기가 1이 됩니다.

이를 일반식으로 바꾸면 1×2^k =n  k가 단계이므로 k=log2의 n이 됩니다.

따라서 merge_sort는 시간복잡도가 O(log n)을 갖습니다. 

이제 merge함수의 시간복잡도를 알아보면 while반복문 1번 for문 1번 이 돕니다. 즉, 대략 2n의 시간복잡도 이므로

O(N)의 시간복잡도를 갖습니다.

전체적인 병합정렬의 시간복잡도는 이둘을 곱해주면 O(N logN)의 시간복잡도를 갖게됩니다.

---

sort함수(c++)

이렇게 몇가지의 정렬알고리즘은 매번 정렬을 할때마다 코드를 쓰기 귀찮습니다.

그래서 c++언어에서는 stl 함수로 sort(정렬)함수를 제공해줍니다. 

코드를 알아보겠습니다.

vector<int>v;
sort(v.begin(), v.end());


int arr[5];
sort(arr, arr+5)

위의 코드는 벡터를 정렬할때, 쓰는 함수이고, 아래는 배열을 정렬할 때 사용하는 함수입니다.

벡터는 sort(정렬하고자 하는 시작구간위치포함, 정렬하고자 하는 끝위치 미포함)

배열은 sort(정렬하고자 하는 시작구간 인덱스 포함, 정렬하고자 하는 끝인덱스 미포함)

이러한 sort함수는 시간복잡도가 O(N log N)을 갖습니다.