chminoo   1년 전

힙이라는 걸 알게된지 조금밖에 안되서 최대한 응용해가면서 하고 있는데요

이건 왜 시간초과가 뜰까요?

heappop을 사용하면 가장 위루트에서 값을 쏙 빼고 하나씩 작은순대로 호로록 올라오니까 pop시킨걸 temp에 넣어놓고 프린트 한뒤에 다시 큐에다가 뺀걸 extend시킨다음 heapify시켜서 힙정렬 해줬습니다

요것들 하나하나가 잡아먹는 복잡도를 잘 몰라서 우선 해봤는데 시간초과가 뜨네용..

sait2000   1년 전

전체 O(n^2 log n)입니다. 12번 줄이 O(n^2)번 실행되니까요. heappop, heappush는 heap의 크기를 n이라 하면 O(log n)이고 heapify는 O(n)입니다.

dyk777   1년 전

힙정렬 없이, 힙의 push와 pop만으로 구현해야 할 겁니다.

힙정렬은 자체 시간복잡도가 O(nlgn)인데, 이를 n개의 원소가 삽입/삭제될때마다 하면 최악 O((n^2)lgn)이 되겠네요.

chminoo   1년 전

아 그렇군요 다들 감사합니다

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