[Algorithms] 비교 기반 sort의 worst case의 lower bound 분석
뭔가 제목이 깨끗하지는 않지만 말 그대로이다. key값의 비교를 기반으로 하는 sort의 worst case의 lower bound가 n log n 이라는 것을 수학적으로 보일 수 있다. 먼저 Decision tree는 yes or no를 선택하는 과정을 tree로 나타낸 것으로 여기에서는 키 값의 비교가 어떠한 decision이 된다. 즉, sort가 진행되는 과정을 decision tree로 나타낼 수 있다. n lgn이 lower bound라는 것을 증명하기 위해서는 몇가지 lemma 필요하다. lemma는 이미 참으로 증명된 정리로써 정리를 증명하는데 사용된다. 첫째, 키값을 기반으로 하는 모든 결정적 정렬 알고리즘의 decision tree는 n! 개의 leaves를 가진다. 둘째, binary..
Computer Science
2011. 7. 7. 20:59
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 자바
- 개발
- Data Science
- 머신러닝
- 리눅스
- Machine Learning
- operating systems
- Discrete Mathematics
- linux
- 운영체제
- reversing
- Data Structure
- 데이터 사이언스
- 데이터 과학
- Reverse Engineering
- android
- 리버싱
- 자료구조
- 안드로이드
- statistical learning
- Algorithms
- 카타르
- 이산수학
- 리버스엔지니어링
- 알고리즘
- 카타르 음주
- 통계학습
- 기계학습
- 대학원
- java
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 29 | 30 | 31 |
글 보관함