글 읽기 - [c언어] 힙정렬 시간초과원인..

tuwis00 5년 전 1

시간초과가되는데 원인이 뭔가요?

#pragma warning (disable:4996)
#include<stdio.h>

void heapify(int N);
void heapsort(int N);

int heap[1000000] = { 0 };

int main() {
	int N;
	scanf("%d", &N);
	for (int n = 0; n < N; n++)
		scanf("%d", &heap[n]);
	heapify(N);
	heapsort(N);
	for (int i = 0; i < N; i++)
		printf("%d\n", heap[i]);
}
void heapify(int N) {
	for (int i = 1; i < N; i++) {
		int c = i;
		do {
			int root = (c - 1) / 2;
			if (heap[root] < heap[c]) {
				int tmp = heap[root];
				heap[root] = heap[c];
				heap[c] = tmp;
			}
			c = root;
		} while (c != 0);
	}
}
void heapsort(int N) {
	for (int i = N - 1; i >= 0; i--) {
		int tmp = heap[0];
		heap[0] = heap[i];
		heap[i] = tmp;
		heapify(i);
	}
}

djm03178 5년 전 1

heapify는 특정 원소 하나에 대해서 그 원소 아래로 힙 상태를 만들어주는 역할이지, N까지의 모든 원소에 대해 이 작업을 수행하는 건 build heap이라고 합니다. heapify는 O(logN) 시간이 걸리고, build heap은 이를 O(N)번 수행하므로 O(NlogN) 시간이 소요됩니다.

처음 원소를 넣어준 상태에서는 build heap을 한 번 해야 하는 것이고, heapsort에서 원소 하나씩을 빼낼 때마다 수행해야 하는 건 heapify입니다. 지금은 둘 모두에서 build heap을 수행하고 있고 heapsort의 루프가 O(N)번 도므로 총 O(N^2logN) 시간이 걸립니다. (버블 소트보다 안 좋습니다.)

tuwis00 5년 전 1

감사합니다 ㅜㅠ!!

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

문제

문제

출처

ICPC

[c언어] 힙정렬 시간초과원인..

tuwis00 5년 전 1

djm03178 5년 전 1

tuwis00 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말