힙소트 우선순위 큐...

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

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.