힙소트 우선순위 큐...
글쓴이: ooshineeoo / 작성시간: 수, 2015/02/25 - 11:18오후
만약 힙소트 우선순위 큐 implementation에서 insert 오퍼레이션이 log(sqrt(n))이 걸리고 extract-max 오퍼레이션이 sqrt(log(n))이 걸린다면 이 큐는 1. comparison 소트가 아니다. 2. implementation이 틀렸다. 3. 러닝타임이 그닥 빠르지 않다. 중 답이 뭔가요? 힌트는 n! ~= (n/e)^n (e는 euler's constant)를 쓰는건데 제가 아는거는 comparison 소트이려면 lower bound가 big-omega(n log n)이라는것밖에...ㅠ
Forums:
잘은 모르지만...
말씀하신 내용이 같은지 확인이 필요합니다.
1. 논리적 코드 검증
플로우 챠트 or 스크렛치 프로그래밍 or 페수드 코드
2. 기능과 데이터 검증 및 가시화 (로그)
코드 및 데이터 디버그 or 그래프 수치 검증 및 확인
3. 전문가의 교육. 용어정리. 참고하거나 따라할만한 예제
울프램 알파로 값을 확인 할 수 있습니다.
http://www.wolframalpha.com/
BigO Cheat Sheet
http://bigocheatsheet.com/
https://docs.google.com/spreadsheets/d/1hyxEEFvF5zBcpC3ALPVPyE8kJ1Soiwd4jpwKjHgzG6o/edit#gid=0
https://drive.google.com/folderview?id=0B9l0_ldK09SOfjE3R1c2LTcxSU8xSGxXNkJpOF9iQ0JMV1NLUDhnUmlXVm50R0tLTGFUeEE
https://drive.google.com/folderview?id=0B9l0_ldK09SOfjE3R1c2LTcxSU8xSGxXNkJpOF9iQ0JMV1NLUDhnUmlXVm50R0tLTGFUeEE
http://aduni.org/courses/algorithms/
stanford
Algorithms: Design and Analysis, Part 1
https://class.coursera.org/algo-004/lecture
Complete Listing
http://www.plouffe.fr/simon/mod1/
Python comparison based sorting
http://www.programering.com/a/MjM2UDNwATg.html
Comparison sort
http://bluemoonsoft.tistory.com/286
http://en.wikipedia.org/wiki/Comparison_sort
----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
...
일단 오타가 아니라는 전제 하에:
1. log(sqrt(n))은 log(n)과 같습니다.
2. Extract-max가 sqrt(log(n))이 걸리는 heap이라는 건 들어본 적이 없습니다. 뭐 제가 모르는 놀라운 신기술이 있을지도 모르겠습니다만...
3. 굳이 답을 고르자면 2번을 고르고 싶은데 (heap에서 sqrt(log(n))이라니 가능한가...?) 문제가 개떡같아서 도대체 뭘 물어보는지 모르겠다는 데 한 표 던집니다.
데이터를 입력하고. 그래프로 디버깅 해보세요.
sqrt(log(n))의 범위가 실제로 원하시는 데이터값의 범위안에 있는지 확인해 보시면 아실 수 있을것 같습니다.
sqrt(log(n)) > Extract-max
WolframAlpha로 그래프의 범위를 확인하 실 수 있습니다.
다른 프로그램 도구를 활용하셔도 될것 같지만. 대학이나 학원. 블로그 전문가분들에게 문의를 해보시는것도 좋을것 같습니다.
----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
댓글 달기