|
:: 게시판
:: 이전 게시판
|
- 모두가 건전하게 즐길 수 있는 유머글을 올려주세요.
- 유게에서는 정치/종교 관련 등 논란성 글 및 개인 비방은 금지되어 있습니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
16/03/02 20:41
학부에서 배우는 퀵소트는 임의의 pivot 하나를 잡고 pivot 보다 작은거/큰걸로 분류하고 이걸 반복하는 형태였다면(이걸 2-way partition quick sort라고 합니다) 퀵3는 3-way partition quick sort를 뜻합니다. 즉, pivot을 하나가 아닌 두개를 임의로 잡고, 이걸 pivot들보다 작은거/두 pivot 사이/pivot들보다 큰거 로 partitioning 한 후 이를 반복합니다. 2-way partition quick sort가 O(nlog_2(n))의 시간복잡도를 가진다면 3-way는 O(nlog_3(n))의 시간복잡도를 가집니다.
16/03/02 20:34
갑자기 깊은 빡침이.......
예전 자바시간에 큐, 리스트, 링크드리스트 등 5가지 저장방식에 대해서 구현하여 결과물을 비쥬얼로 PT하라 해서 프로그램으로 하나 하나 구현했더니 보시고 하시는 말씀이 야 있는 class 나두고 왜 만들어? 자바클래스 몰라? 왜 쓸데없이 시간 보내냐! 아오 ~~~~! 누가 몰라 구현하라니까 했지 ~~~~!
16/03/02 21:52
저 이미지에서는 메모리 접근이 모두 똑같이 걸리게 표현하고 있어서 시간복잡도상 접근횟수가 적은 힙정렬이 유리합니다.
실제로는 힙 자료구조의 특성상 인접한 메모리 접근을 거의 하지 않기 때문에 메모리 캐싱같은 부분에서 불리해서 다른 nlogn 알고리즘에 비해 성능이 떨어진다고 합니다.
|
||||||||||||||
