후로링의 프로그래밍 이야기

비교기반의 정렬알고리즘은 어떤 경우에도 O(n logn)보다 빠를 수 없습니다. 이를 증명하하는것으로 Sorting 부분은 넘어가도록 하겠습니다. Insertion Sort, Heap Sort, Quick Sort, Counting Sort, Radix Sort, Bucket Sort등등은 인터넷상에 자료가 많습니다. 혹시라도 잘 모르시는분들은 찾아서 해보시면 되겠습니다. Sort가 진행되는 과정은 Decision Tree로 나타낼 수 있습니다. 증명에는 몇가지 Lemma(참으로 증명된 정리)가 필요합니다. 1. 모든 정렬 알고리즘의 decision tree는 n!개의 Permutation(순열)을 가진다. (다시말해, 정렬이 될 수 있는 모든 경우의 수가 n!이란 뜻입니다. ) 2. Binary tre..

Binomial Heap을 배우기 위해서 Binomial Tree가 어떤 것인지 부터 알아보겠습니다. Binomial Tree Binomial Tree는 우선순위 큐 형태의 자료구조입니다. 아래 그림과 같이 한 Tree의 루트 노드가 다른 루트 노드를 가리키는 형태입니다. 노드의 수는 2^k(루트에 새로 붙여지는 트리와 붙는 트리의 크기가 같다), 루트에 붇기 때문에 높이는 1씩 증가하게되며 트리의 깊이는 K combination i(K에서 i를 뽑는 경우의수), 그리고 루트의 degree가 가장 크게 됩니다. Binomial Heap Binomial Heap의 각각의 Binomial Tree는 min-heap입니다. 그리고 k값이 같은 Binomial Tree는 존재하지 않습니다(차수가 같은 트리가 존..