글 읽기 - 오잉 병합정렬로 짯는데 왜 시간초과인가요??...

jumpingz 6년 전 0

병합정렬로 해결하려고 했는데 시간초과가 발생하네요..?

빅오 계산으로는 안날것 같은데. 최악의 경우가 존재하는건가요?

#include <cstdio>
#include <vector>

using namespace std;

void Divide(vector<int> &v, int s, int e, int N);
void Sort(vector<int> &v, int s, int m, int e, int N);

int main()
{
	int N;
	scanf("%d",&N);
	
	vector<int> v(N);
	for(int i = 0; i < N; i++)
		scanf("%d",&v[i]);
		
	Divide(v,0,N-1,N);	
	
	for(int i = 0; i < N; i++)
		printf("%d\n",v[i]);
	
	
	
	return 0;
}

void Divide(vector<int> &v, int s, int e, int N)
{
	if(s < e)
	{
		int mid = (s + e) >> 1;
		Divide(v,s,mid, N);
		Divide(v, mid + 1,e, N);
		Sort(v,s,mid,e, N);
	}
}

void Sort(vector<int> &v, int s, int m, int e, int N)
{
	int L = s, R = m + 1, start = s;
	vector<int> T(N);
	
	while(L <= m && R <= e)
	{
		if(v[L] < v[R])
			T[start++] = v[R++];
		else
			T[start++] = v[L++];
	}
	
	if(L > m)
		for(; R <= e; R++)
			T[start++] = v[R];
	else
		for(; L <= m; L++)
			T[start++] = v[L];
	
	for(int i = s; i <= e; i++)
		v[i] = T[i];
}

onjo0127 6년 전 0

Sort 함수 안에서 크기 N의 T라는 벡터를 계속 만들고 있는데, 저러면 Sort함수가 NlogN번 호출되기 때문에 시간복잡도가 NlogN * N = N^2logN이 됩니다.

jumpingz 6년 전 1

아 저런작업이 내부에 오버헤드가 걸리는군요.. 새로운걸 또 알아갑니다 감사합니다.

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

문제

문제

출처

ICPC

오잉 병합정렬로 짯는데 왜 시간초과인가요??...

jumpingz 6년 전 0

onjo0127 6년 전 0

jumpingz 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말