학교강의필기장

Quick Sort는 Merge Sort와 같이 분할정복을 이용한 정렬법이지만, 공간을 n만큼 더 사용하는 merge sort와 달리 in-place sort 입니다. pivotpoint가 항상 맨 앞일 때를 가정한 코드는 다음과 같습니다. int partition(int S[], int low, int high){ int pivotpoint = low; int j=low; for(int i=low+1; i

알고리즘은 아니지만, 재귀 문제의 시간 복잡도를 계산하는데에 큰 도움이 되는 theorem입니다. 위와 같은 식이 있을 때, master theorem에서 필요한 값은 a와 b, f(n)입니다. 여기서 3가지 경우로 나누어집니다. ε는 0이상의 상수이며, f(n)이 어느 식에 해당하는지 확인해야 합니다. 먼저 Case 1과 Case 2에 해당할 때엔, 간단하게 위와 같은 시간 복잡도가 구해집니다. 다만 Case 3일때는 추가적인 조건이 필요합니다. 위에서 제시한 Case3 조건과 위 조건에 전부 해당하면 시간 복잡도는 위와 같습니다. Case 1,2,3에 속하지 않다면, 위의 Auxiliary Master Theorem를 참고하시길 바랍니다.

병합정렬은 분할정복을 이용한 sort algorithm입니다. 먼저 배열을 1개 단위로 쪼갠 뒤, 다시 합치며 정렬하는 방법입니다. 코드는 다음과 같습니다. void merge(int S[], int U[], int low, int mid, int high){ int i=low, j=mid+1, k=low; while(i

이분탐색은 오름차순 정렬된 배열에서 특정 값을 찾아 인덱스를 반환하는 search algorithm입니다. 코드는 다음과 같습니다. int binarySearch(int A[], int x, int low, int high){ int mid; if(low>high) return -1; else{ mid = (low+high)/2; if(A[mid]==x) return mid; else if(A[mid]>x) return binarySearch(A,x,low,mid-1); else return binarySearch(A,x,mid+1,high); } } low와 high의 초기값은 각각 탐색하고자 하는 배열의 처음 인덱스와 마지막 인덱스입니다. 즉 mid는 현재 탐색하고 있는 배열의 가운데 인덱스를 가리키..