wjdtmdrbs88   8년 전

예전에는 우선순위큐를 이용한 힙 구현으로 문제를 풀었는데


학교에서 LinearSelect이라고 하는 선형시간이 걸리는 알고리즘을 배워서 그걸 적용 해보았더니, 21%까지는 잘가다가 거기서 시간초과가 뜨더라구요.

혹시 시간복잡도에 대해 자세히 아시는 분들 설명좀 해주실수 있나요 ??? 일단 최악의경우도 n 이라더라구요 리니어 셀렉이

힙은 nlogn이라고 알고있는데도 답이 뜨는데 흠 ..

koosaga   8년 전

O(n)이 맞긴 한데, 성능 향상을 보려면 좀 구현에 공을 많이 들여야 할거에요

wjdtmdrbs88   8년 전

일단 학교에서 사용하는 저지에서는 리니어셀렉의 구현에대한 문제에 어셉을 받아서 내보았는데 시간초과가나네요 ㅠㅠ

koosaga   8년 전

전 linear selection algo에 대해서 잘 몰라서, 그걸 도움드리긴 힘들거 같고

다만 흑마법 (?) 이라고 하면, 아마 입력을 scanf로 해도 많이 느릴텐데, 제 0.1 소스를 한번 참고해서 빠르게 입력받아보세요. 백점이 아니어도 제 소스는 받을 수 있어요

noru0114   6년 전

https://en.wikipedia.org/wiki/Quickselect

quick select 말하신거면 여기에 시간복잡도가 나와있습니다

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