힙소트 우선순위 큐...

ooshineeoo의 이미지

만약 힙소트 우선순위 큐 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)이라는것밖에...ㅠ

shint의 이미지

말씀하신 내용이 같은지 확인이 필요합니다.

1. 논리적 코드 검증
플로우 챠트 or 스크렛치 프로그래밍 or 페수드 코드

2. 기능과 데이터 검증 및 가시화 (로그)
코드 및 데이터 디버그 or 그래프 수치 검증 및 확인

3. 전문가의 교육. 용어정리. 참고하거나 따라할만한 예제

//페수드 코드
 
hsi = heap_sort_insert( n );
ls = log( sqrt(n) );
if( hsi > ls )
{
   find_hsi = true;
}
 
em = extract-max( n );
sl = sqrt( log(n) );
if( em > sl )
{
   find_em = true;
}
 
if( find_hsi == true && find_em )
{
    //힌트 n! ~= (n/e)^n    //euler's constant 오일러 상수
 
    if( comparison == not_sort ) //비교 정렬이 아니다.
    {
        //real?
    }
    else
    {
        //lower bound == big-omega(n log n)
    }
 
    if( implementation == false ) //구조가 틀리다.
    {
        //real?
    }
 
    if( running_time == slow ) //실행 시간이 느리다.
    {
        //real?
    }
}

울프램 알파로 값을 확인 할 수 있습니다.
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

jick의 이미지

일단 오타가 아니라는 전제 하에:

1. log(sqrt(n))은 log(n)과 같습니다.
2. Extract-max가 sqrt(log(n))이 걸리는 heap이라는 건 들어본 적이 없습니다. 뭐 제가 모르는 놀라운 신기술이 있을지도 모르겠습니다만...
3. 굳이 답을 고르자면 2번을 고르고 싶은데 (heap에서 sqrt(log(n))이라니 가능한가...?) 문제가 개떡같아서 도대체 뭘 물어보는지 모르겠다는 데 한 표 던집니다.

shint의 이미지


sqrt(log(n))의 범위가 실제로 원하시는 데이터값의 범위안에 있는지 확인해 보시면 아실 수 있을것 같습니다.

sqrt(log(n)) > Extract-max

WolframAlpha로 그래프의 범위를 확인하 실 수 있습니다.
다른 프로그램 도구를 활용하셔도 될것 같지만. 대학이나 학원. 블로그 전문가분들에게 문의를 해보시는것도 좋을것 같습니다.

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com