공대생 정리노트

Hashing 어떠한 key값이 주어지면 그 key 값으로 상수시간에 원하는 값을 찾을 수 있게 하는 것이 Hashing이다. record 값을 담고 있는 Hash table을 이용하는데, 이 Hash table을 편의상 HT라고 하자. HT가 가지고 있는 slot의 개수를 M개라고 하자. 우리는 key 값을 mapping하는 Hash function을 이용한다. 이 hash function을 h라고 하자. 어느 key 값 K가 주어졌을 때 h(K)의 범위는 다음과 같다. 0 1) key가 짝수만 들어온다면 홀수 slot들은 쓰이지 않는다 2) K가 큰 값이면 모든 bit를 사용하지 않고 마지막 bit 4개만 사용한다. 이러한 이유로 좋은 hash function이 아니다. 1) 해결 방법 : M을 소수..

Heuristics self-organizing lists는 패턴에 기반하여 record를 정렬한다. 이때 어떻게 정렬할지에 대하여 Heuristic을 사용하게 된다. 자주 사용하는 item을 앞으로 오게 하는 것이 idea이다. Heuristics 예 처음에 ABCDEFGH로 정렬된 record를 가지고 있다고 생각해보자. Access pattern은 F D F G E G F A D F G E 순으로 왔다고 가정하자. 1. Count Heuristic historical frequency에 기반하여 정렬한다. 2. Move-to-front Heuristics 최근 access한 record를 제일 앞에 정렬한다. 3. Transpose Heuristic 맨 앞으로 옮기는 것이 아닌 바로 앞에 있는 re..

Jump Search Ordered Array에 대하여 search를 할 때 k의 배수번째 element만 check를 한다. 만약 check한 element가 찾고자 하는 원소의 value보다 작다면 계속 진행한다. 그렇지 않다면 그 전 원소들에 대하여 linear search를 진행한다. Analysis of Jump Search input size가 n이라고 하자. 만약 (m-1)k

Time Complexity comparison-based sorting은 time complexity의 lower bound가 O(nlogn)이다. n개의 element가 있는 array가 있을 때 나올 수 있는 permutation의 수는 n!이다. sorting algorithm은 이 permutation들 중 올바른 유일한 permutation을 하나 고르는 것이다. decision tree에서 permutation은 각각의 leaf node에 위치하게 된다. 그렇다면 어떠한 comparison based sorting algorithm은 n!개의 leaves를 가져야 한다. n!개의 leaves를 가지는 tree의 depth는 어떨까? n개의 node를 가지는 tree의 level은 Ω(logn..

Heapsort Heap data structure를 이용하는 sort max heap을 이용한다면 removemax를 n번하여 정렬한다. removemax의 cost가 원소가 n개 있을 때 O(logn)이 걸리므로 Heapsort의 cost는 다음과 같다. O(n) (Heap을 만드는데 cost) + O(logn) + O(log(n-1)) + O(log(n-2)) + ... + O(log(1)) = O(nlogn) Binsort 원소의 범위가 0부터 n-1까지만 있을 때 가능한 Sort. MaxKey Value를 길이로 가진 배열을 만든다. 그 배열은 원소로 linked list를 가진다. 그러면 정렬할 permutation을 앞에서부터 보면서 해당하는 linked list에 집어넣는다. 예를 들어 p..

Merge Sort array를 반으로 자르고 반으로 잘린 array를 각각 정렬한 후 정렬된 값들을 합친다. Divide and Conquer 접근법의 예. 각각의 정렬에서 O(n)이 걸리고 정렬의 총 횟수는 logn이므로 O(nlogn)의 cost를 가지게 된다. best, average, worst cases에서 모두 O(nlogn)의 cost를 가진다. Quick Sort Divide and Conquer 접근법을 사용하는 또다른 예이다. array에서 기준이 되는 한 값을 선택한다(pivot 선택). 그리고 pivot을 기준으로 pivot보다 작은 값들은 pivot 왼쪽에 정렬하고, 큰 값들은 pivot 오른쪽에 정렬한다.(partition operation) partition의 cost는 O(..

Selection Sort 가장 작은 원소를 array의 앞에 놓는 것은 bubble sort와 유사하다. 다만 bubble sort는 원소를 옮길 때 주변의 원소와 위치를 바꾸는 것을 반복하여 옮기는 반면, selection sort는 array를 scan하여 가장 작은 원소를 찾고 array의 가장 첫번째 원소와 위치를 바꾼다. 가장 작은 원소의 index를 찾아야 하기 때문에 i번째 iteration 마다 n-i번의 비교를 하게 된다. Best Case : 0번 위치 바꿈, O(n^2/2)번의 비교 Worst Case : n-1번의 위치 바꿈, O(n^2/2)번의 비교 Average Case : O(n)번의 위치 바꿈, O(n^2/2)번의 비교 Bubble Sort와 비교하면 위치를 바꾸는 횟수가 ..

Insertion Sort 처음에는 output은 비어있다. item을 하나씩 넣으면서 적절한 자리를 골라 채운다. 한 item의 적절한 자리를 찾을 때, 그 전까지 들어간 item들은 정렬이 되어 있으므로 넣는 item의 값보다 작은 item이 나올때까지 앞의 item과 자리를 계속 바꾼다. Best Case(이미 정렬되어 있는 경우) : 자리 바꿈 0번, n-1번 comparisons Worst Case(역순 정렬되어 있는 경우) : 자리 바꿈과 comparisons 둘 다 O(n^2/2)번 Average Case : 자리 바꿈과 comparisons 둘 다 O(n^2/4)번 insertion sort는 대다수의 경우 그렇게 효율적이지 못하지만 거의 정렬되어 있는 array에 대해서 정렬을 할 때는 ..