인프런 커뮤니티 질문&답변
작성한 질문수
시간 복잡도 문의드립니다.
작성
·
216
1
최소힙 -> 최대힙으로 바꾸면서 시간복잡도 개선이있다고 생각하고 저도 어떤말씀이신지 이해가 돼었습니다.
다만 해당문제를 릿코드에서 돌려보면 결과는 그 반대입니다.
위가 최소힙 구현코드
아래가 최대힙 구현코드인데 왜 이런결과가 나오는지 궁금합니다.
ps. 여러번 돌려도 runtime결과는 +- 1ms 내외입니다.
답변 1
0
푸샵맨 코딩스터디
지식공유자
고성빈님 반갑습니다~
좋은 질문 감사합니다.
제가 개선사항으로 찾아보자고 해서 Nlog N ->Nlog K로 했는데
이론적으로는 nlog K가 더 빨를거 같지만 그렇지 않은 경우네요 ㅜㅜ
log n은 n개를 전부 저장하는거고
log k는 n개를 다 저장하지 않고 사이즈를 계산해서 삭제해서 k개 만큼 저장하다 보니
이론적으로는 n logk가 더 빠르다고 생각했는데
pq.size(), pq.poll()하면서 더 리소스를 쓰고 있네요
이부분 추후 업데이트하도록 하겠습니다.
체크 감사합니다.
아 그리고 , 이 문제는 nlogn과 nlogk를 면접에서 많이 물어봅니다.
k개 만큼만 저장해보라고 면접관이 요청할 수 있습니다.
