시간 복잡도 문의드립니다.

Question

최소힙 -> 최대힙으로 바꾸면서 시간복잡도 개선이있다고 생각하고 저도 어떤말씀이신지 이해가 돼었습니다. 다만 해당문제를 릿코드에서 돌려보면 결과는 그 반대입니다. 위가 최소힙 구현코드 아래가 최대힙 구현코드인데 왜 이런결과가 나오는지 궁금합니다. ps. 여러번 돌려도 runtime결과는 +- 1ms 내외입니다.

pushupman · Answer

고성빈님 반갑습니다~ 좋은 질문 감사합니다. 제가 개선사항으로 찾아보자고 해서 Nlog N ->Nlog K로 했는데 이론적으로는 nlog K가 더 빨를거 같지만 그렇지 않은 경우네요 ㅜㅜ log n은 n개를 전부 저장하는거고 log k는 n개를 다 저장하지 않고 사이즈를 계산해서 삭제해서 k개 만큼 저장하다 보니 이론적으로는 n logk가 더 빠르다고 생각했는데 pq.size(), pq.poll()하면서 더 리소스를 쓰고 있네요 이부분 추후 업데이트하도록 하겠습니다. 체크 감사합니다. 아 그리고 , 이 문제는 nlogn과 nlogk를 면접에서 많이 물어봅니다.  k개 만큼만 저장해보라고 면접관이 요청할 수 있습니다.