with with

Thresholds Merge Sort, Exchange Sort를 예로 들어보자. merge sort의 time complexity는 n lg n 이었다. exchange sort는 이중 반복문을 통한 정렬 방법으로 n^2의 time complexity를 갖는다. 대부분의 경우에는 merge sort를 사용하는 것이 더 시간이 적게 걸릴 것이다. 하지만, n의 크기가 작은 경우에는 exchange sort를 사용하는 것이 더 효율적일 수 있다. 그 이유는 merge sort가 동작함에 있어 아래와 같은 기능은 오버헤드가 있기 때문이다. mid 계산 재귀함수 호출 시, call stack에 2개의 함수를 추가 2개의 subArray를 merge 따라서 Thresholds를 정해 입력의 갯수 n이 특정 수..

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 기본적인 방식은 Merge Sort와 동일하다. 다만, 배열을 반으로 분해하는 것이 아닌, 배열 내부에서 원소의 위치를 이동시키기 때문에 Combine part가 필요가 없어진다. (붉은 원이 pivotItem, pivotItem보다 √ 가 작을 경우 ++j와 √ 의 위치를 변경, 마지막에 pivotItem과 j의 위치를 변경, 위 과정을 재귀 호출) - Pseudocode // S: global public static void quickSort (index low, index high) { if (high

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 주어진 배열을 정렬하는 알고리즘. 단, 정렬하는 방법이 Divide and Conqure 방식이다. 배열을 최대한 작게 쪼개고, 병합하는 과정에서 정렬하여 병합하는 방식이다. - Pseudocode public static void mergeSort (int n, keyType[] S) { if (n

- 정의 이전 두 항의 합이 다음항이 되는 수열이다. - Pseudocode // Iterative way public static int IterFib (int n) { index i; int[] f = new int[n+1]; if (n

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 정렬이 된 배열에서 찾고자 하는 원소가 나올 때 까지 탐색하는 알고리즘. 탐색하는 방법은 low, high의 가운데, mid와 비교하여 찾고자 하는 값이 mid보다 크면 오른쪽, 작으면 왼쪽의 배열에서 다시 탐색한다. - Pseudocode // Iterative way public static index BinSearch (int n, keyType[] S, keyType x) { index location, low, high, mid; low = 1; high = n; location = 0; while (low

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 찾고자 하는 원소가 나올 때 까지 인덱스의 처음부터 순차로 탐색하는 알고리즘. - Pseudocode public static index SeqSearch(int n, keyType[] S, keyType x) { index location = 1; while (location n) location = 0; return location; } 크기가 n인 배열 S에서 x를 찾는 알고리즘. location이 n보다 작거나 x를 발견하지 못할 경우 location을 1씩 증가하며 탐색 찾은 경우, 또는 배열의 끝까지 탐색한 경우 while문을 빠져나온다. 끝까지 탐색한 경우에는 location을 ..

재귀함수를 이용하여 구현된 알고리즘의 경우 시간 복잡도 함수를 구하다 보면 재귀식으로 이루어진 시간 복잡도 함수를 마주하게 된다. 이런 경우 재귀식을 일반식으로 수정해야 하는데, 그 방법을 알아보자. * 선형인 재귀식의 경우만을 다룹니다. - Homogeneous case f(n) = 0 인 형태의 식을 homogeneous라고 하는데, 이런 경우의 재귀식을 계산하는 법을 알아보자. 위 식을 생각해보자. tk 항으로 이루어진 재귀식이다. 이 경우 아래와 같은 특성 방정식(characteristic equation)으로 변환 가능하다. 여기서 두 가지 경우로 나뉘는데, (r-1)(r-2)(r-3) 처럼 중근을 갖지 않는 경우와 (r-1)(r-2)^2 처럼 중근을 갖는 경우로 나뉘게 된다. * 중근을 갖지 ..

Time complexity 시간 복잡도는 알고리즘이 수행되는 데 걸리는 시간을 의미하며, 시간 복잡도가 클 수록 알고리즘이 수행 되기까지 걸리는 시간이 길다는 것을 의미한다. 시간 복잡도를 계산하기 위해선 2개의 파라미터가 필요하다. - Input size 입력으로 들어온 값의 크기를 의미한다. 입력으로 들어온 값은 배열일 수도, 특정 값이나 문자열, 혹은 graph와 같이 vertices, edges가 들어올 수 있다. - Basic operation 알고리즘은 여러 줄의 코드로 이루어진다. 그 중 핵심이 되는 코드를 기본 연산으로 삼아서 시간 복잡도를 계산한다. 예로 들어 순차 탐색 알고리즘의 경우에는 배열의 특정 index와 찾고자 하는 값의 비교 연산이 이에 해당한다. 시간 복잡도 분석은 모든 ..