일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 |
- OpenCL
- Memory Leak
- Device
- OpenCL 설치
- program
- 메모리 누수
- Queue
- OpenCL 2.0
- Platform
- Intel OpenCL
- OpenCL 2.0 시작하기
- initialize
- init
- Kernel
- Visual Leak Detector
- OpenCL 초기화
- VLD
- Today
- Total
목록2017/02 (2)
후로링의 프로그래밍 이야기
비교기반의 정렬알고리즘은 어떤 경우에도 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는 존재하지 않습니다(차수가 같은 트리가 존..