whazzulookinat   1년 전

C를 이용해 BST 구현을 하였고, 특히 insert 과정에서 입력이 worst case로 되는 경우(1,2,3,4,5,6)를 방지하기 위해 정렬 후 중간부터 옆으로 하나씩 이동하면서 넣어주며 balancing property를 유지해주었습니다. 그런데도 계속 시간초과가 뜨네요.. 혹시 어떤 부분이 시간초과를 초래했을까요..

djm03178   1년 전

이 문제는 시간복잡도에 로그를 붙여서는 통과하기 어렵습니다. 해싱으로 평균 O(1)에 풀기를 의도한 문제입니다. 그래도 시간이 매우 빠듯합니다.

greedev   1년 전

머지소트 + 이분 탐색으로 풀립니다

djm03178   1년 전

채점 서버가 많이 빨라지긴 했군요. 로그를 쓴다면 아마 상수를 많이 최적화해야 될 거고, fast I/O도 도움이 많이 될 것 같습니다.

cubelover   1년 전

  1. qsort는 최악의 경우 O(n^2)입니다. 이 문제에 qsort 저격 데이터가 있는지는 확실치 않으나, 저격 데이터가 있을 경우 이 부분에서 O(n^2)이 되었을 수 있습니다. C++ STL의 std::sort를 사용하거나 머지 소트 등 다른 방법을 사용해 보세요.
  2. 중간부터 삽입한다고 해도, 연속적으로 삽입하면 트리는 균형잡힌 이진 트리 형태가 아니라 V자 형태가 됩니다. 따라서 시간복잡도가 O(n^2)이 됩니다. 균현잡힌 이진 트리 형태로 만들어지도록 삽입 순서를 바꾸거나, AVL 트리 또는 Red-Black 트리와 같은 자료구조로 바꿔 보세요.

cubelover   1년 전

근데 이 문제 정말로 O(N log N)과 O(N)을 구분하려고 한 문제면 🐛네요...

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