공대생 정리노트

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에 대해서 정렬을 할 때는 ..

General Trees Traversal General Tree에서 Preorder Traversal과 Postorder Traversal은 정의가 된다. 그러나 Inorder Traversal은 binary tree에서는 정의가 되지만 non binary tree에서는 정의가 되지 않는다. Equivalence Class Problem 임의의 두 노드를 골랐을 때 두 노드가 같은 tree에 있는지 다른 tree에 있는지 어떻게 알아낼 수 있을까? 각 노드의 root를 비교해서 같다면 같은 tree에 있을 것이고, 다르다면 다른 tree에 있는 것일 것이다. 이때 root를 알아내는 operation을 Find라고 한다. 실제 생활에서 사용되는 예로는 SNS에서 나와 다른 사람이 공통적으로 아는 사람이..

어떠한 구조인가? data를 입력 받을 수 있으면서 request가 들어오면 제일 큰 값을 반환할 수 있는 구조 Implementation 1. Unsorted array or linked List Insert : O(1) removemax : O(n) 2. Sorted array or linked list Insert : O(n) removemax : O(1) 위 두 개의 구현 모두 O(n)이 걸리는 함수가 존재하여 효율적이지 못하다. 이를 해결하기 위하여 heap이 등장한다. 3. heap Insert : O(logn) removemax : O(logn) Heap Heap이란 ? complete binary tree의 일종이다. Min-heap : 모든 value는 child value보다 작다. M..

Array Implementation Binary Search Tree는 Array로 표현할 수 있다. 위와 같은 Binary Tree는 다음과 같이 표현할 수 있다. 현재 있는 position number를 r이라고 하자. 그렇다면 그 position의 parent와 child, sibling은 다음과 같다 Parent(r) = floor((r-1)/2) Leftchild(r) = 2r+1 Rightchild(r) = 2r+2 Leftsibling(r) = r-1 Rightsibling(r) = r+1 BST and Traversal 앞의 게시글에서 나왔던 Traversal들 중 inorder traversal를 BST에 적용하면 정렬이 된 순서로 element를 얻을 수 있다. Inorder Trav..