5개의 댓글이 있습니다.

• 
  Toivoa

  Quick sort에서 사용하는 partition 방식을 이용해서 armortized O(N) 으로 찾을 수 있는 방법이 있습니다. STL에도 nth_element로 구현되어 있으며, 자세한 내용은 Introduction to Algirithm (CLRS) 등과 같은 책을 참고해보세요.

  
  13년 전 link

• 
  MiNu

  O(n)에 k-th element를 찾아낼 수 있는 방법이 있다고 알고 있습니다.
  자세한 내용은 "Introduction to Algorithms - Chap.9.3 Selection in worst-case linear time" 을 보시면 될거같네요ㅎㅎhttp://books.google.com/books?id=NLngYyWFl_YC&pg=PA189&dq=Selection+in+worst-case+linear+time#v=onepage&q=Selection%20in%20worst-case%20linear%20time&f=false

  
  13년 전 link

• 
  MiNu

  아아.. STL의 nth_element도 그런 방식으로 구현되어 있었군요...ㅎㅎ

  
  13년 전 link

• 
  오버액션

  오오 감사합니다. ^^

  
  13년 전 link

• 
  JongMan

  위키피디아 보셔도 됩니다. ^^ http://en.wikipedia.org/wiki/Selection_algorithm

  
  13년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.