tjdgns9246   5달 전

다음과 같이 첫번째 배열은 정렬을 해준 뒤 이진탐색으로 검색을 했습니다.

그런데 시간초과가 뜨네요... 어떻게 해야 할 지 모르겠습니다.

도움 좀 주실 분 계신가요?

indioindio   5달 전

선택정렬은 너무 느리지 않을까 싶네요

opencv   5달 전

STL에서 제공하는 sort 함수를 사용해보시는건 어떠신가요?

tjdgns9246   5달 전

indioindio님, 코드를 실행했을 때 걸리는 시간을 제한시간이랑 비교를 어떻게 하나요?

시간복잡도라는 걸 잠깐 공부했긴 했었는데... 정확한 개념을 이해하지 못하겠더라구요.

어떤 기준으로 느리다고 생각하신건가요?


opencv님, STL에서 제공하는 sort함수는 어떤건가요?

indioindio   5달 전

글쎄요 경험적으로 본다면 작성하신 selectionSort를 gcc -O2 로 컴파일한 다음 임의로 생성한 100000개의 입력에 대해 실행하였을 때 6.3초 정도 걸립니다. (최적화 옵션을 끄면 22초 정도 걸리네요)

시간복잡도 측면에서 볼 때, 선택정렬은 O(n^2)입니다. 정확한 설명은 절대 아니지만, 대충 입력의 크기에 따라 걸리는 시간의 증가양상이 n^2의 그래프와 흡사하다 정도로 이해하시면 될 것 같습니다. 모 책에서는 시간복잡도에 입력의 크기를 대입해서 얻은 값에 대해서, 1억 당 1초가 걸린다고 생각하면 된다고 합니다. 10만^2는 100억이니 이 방법으로 계산하면 100초가 걸립니다. (차이가 좀 있지만... 근사값이기도 하고, 선택정렬은 상수요소가 적기도 하고, 제한시간은 초과한다 정도로 이해하시면 될 것 같습니다.) 

stl 의 sort는 구현체에 따라 다르겠지만 보통 퀵소트+힙소트로 구현되어 있는 것 같네요. 퀵정렬이나 힙정렬은 O(NlogN)의 복잡도를 갖는데요, 위의 계산법에 따르면 1660964의 값을 가지니 1초 내에 들어오리라고 예상할 수 있겠죠.

indioindio   5달 전

돌려보니 약 0.05초정도 걸리네요

tjdgns9246   5달 전

indioindio 님, 덕분에 좋은 정보 알아갑니다 ^^ 감사합니다.

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