lsh9034   5년 전

quick selection인가요? 퀵소트를 응용한 셀렉션을 그대로 구현해서 풀긴했는데요. 다른 분들 소스를 보니까 nth_element()  ?이거를 쓰셔서 풀었는데 검색해보니까 퀵 셀렉션이더라구요. 아무리 라이브러리 함수라지만 10배 이상 차이가 나는건 좀 의문이 들어서요.. 제 코드는 1260ms인데 다른 분들을 막 100ms... 제 코드의 어디가 문제가 있는건지 질문드립니당.. ㅠㅠ

doju   5년 전

이 코드는 이미 정렬된 배열에서 첫 번째 값을 찾으려고 할 때 아주 비효율적으로 동작합니다. 아직 이런 데이터가 없었다는 것이 놀랍네요.
이런 상황을 방지하기 위해 보통 중간값에 가까운 값을 찾아서 피벗으로 잡거나 아예 배열을 랜덤하게 섞는 등의 방법을 사용합니다.

댓글을 작성하려면 로그인해야 합니다.