alsrl9   3년 전

배열로 Heap 정렬을 구현해서 문제를 해결하려고 하는데

같은 C언어로 문제를 해결하신 분들보다 응답시간이 훨씬 오래 걸립니다.

배열을 사용해서 문제를 해결하되, 응답시간을 줄이고 싶습니다.

제 실력이 부족해서 다른 분들의 코드를 이해하진 못했지만

배열이 아닌 리스트 구조를 만드셔서 문제를 해결하신 것 같습니다.

리스트 구조가 더 유리한 것인지 제가 구현한 방식이 문제인 것인지 모르겠습니다.

방향을 잡을 수 있도록 도와주시면 감사하겠습니다.

djm03178   3년 전

원칙적으로 원소를 추가할 때마다 realloc을 하는 방식은 선형 시간 복잡도 자체가 보장되지 않습니다. 최악의 경우 메모리를 새로운 위치에 할당하고 기존 내용을 전부 복사해서 옮겨야 하기 때문입니다. 다만 대개의 경우 그런 일이 너무 자주 발생하지 않을 수 있도록 메모리 관리 함수들이 잘 짜여져 있기 때문에 그보다는 빠르게 동작하는 것입니다.

alsrl9   3년 전

감사합니다. 어떤 점이 문제인지 알 것 같아요.

리스트나 다른 방법을 이용해서 heap 정렬을 구현해보겠습니다.

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