lg970325   7년 전

퀵소트로 정렬했는데...

시간초과 뜨네요...

june020615   7년 전

퀵소트의 경우에도 시간복잡도가 O(n2) 가 나오는 경우가 있을 수 있어요. 이 문제의 경우는 합병정렬을 사용하시는 것이 좋을 듯 하네요. 합병정렬의 경우는 시간복잡도가 최악의 경우에도 O (n logn) 인 걸로 알고 있습니당

cseteram   7년 전

N이 500백만이라 배열 전체에 정렬을 수행하면 시간 초과가 뜰 겁니다.

k번째 원소를 찾는데 최악의 경우에도 theta(n)을 보장하는 알고리즘이 있어요. 예시로는 BFPRT가 있겠네요.
https://en.wikipedia.org/wiki/Median_of_medians

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