퀵소트의 경우에도 시간복잡도가 O(n2) 가 나오는 경우가 있을 수 있어요. 이 문제의 경우는 합병정렬을 사용하시는 것이 좋을 듯 하네요. 합병정렬의 경우는 시간복잡도가 최악의 경우에도 O (n log2 n) 인 걸로 알고 있습니당
11004번 - K번째 수
퀵소트의 경우에도 시간복잡도가 O(n2) 가 나오는 경우가 있을 수 있어요. 이 문제의 경우는 합병정렬을 사용하시는 것이 좋을 듯 하네요. 합병정렬의 경우는 시간복잡도가 최악의 경우에도 O (n log2 n) 인 걸로 알고 있습니당
N이 500백만이라 배열 전체에 정렬을 수행하면 시간 초과가 뜰 겁니다.
k번째 원소를 찾는데 최악의 경우에도 theta(n)을 보장하는 알고리즘이 있어요. 예시로는 BFPRT가 있겠네요.
https://en.wikipedia.org/wiki/Median_of_medians
댓글을 작성하려면 로그인해야 합니다.
lg970325 7년 전
퀵소트로 정렬했는데...
시간초과 뜨네요...