글 읽기 - 수행속도 차이가 왜 이렇게 크게나는지 모르겠습니다(모스 알고리즘)

kdr06006 4년 전 0

모스알고리즘을 공부중인데, 두 코드의 수행속도 차이에 대해 질문드립니다.

25, 26번째 줄을

if (query[i].s < query[j].s) temp[k++] = query[i++];

else if (query[i].s == query[j].s && query[i].e < query[j].e) temp[k++] = query[i++];

이런 식으로 짜면 800ms나 걸리는데 아래 코드와 같이 바꾸면 100ms로 줄어듭니다.

왜 이렇게 큰 차이가 나는지 잘 모르겠습니다.

#include<stdio.h>

const int _size = 1e5 + 1;
int sqrtN;

typedef struct Query {
	int s, e, n;
}Q;
Q query[_size], temp[_size];
int arr[_size], res[_size];

int sqrt(int n)
{
	double ret = n;
	for (int i = 0; i < 16; i++) {
		ret = ret - (ret * ret - n) / (ret * 2);
	}
	return (int)ret;
}

void merge(int left, int right, int mid)
{
	int i = left, j = mid + 1, k = left;
	while (i <= mid && j <= right) {
		if (query[i].s / sqrtN < query[j].s / sqrtN) temp[k++] = query[i++];
		else if (query[i].s / sqrtN == query[j].s / sqrtN && query[i].e < query[j].e) temp[k++] = query[i++];
		else temp[k++] = query[j++];
	}
	while (i <= mid) temp[k++] = query[i++];
	while (j <= right) temp[k++] = query[j++];

	for (int l = left; l <= right; l++) query[l] = temp[l];
}

void divide(int left, int right)
{
	if (left >= right) return;
	int mid = (left + right) / 2;
	divide(left, mid);
	divide(mid + 1, right);
	merge(left, right, mid);
}

int main(void)
{
	int N, M, n1, n2;
	scanf("%d %d", &N, &M);
	sqrtN = sqrt(N);

	for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &n1, &n2);
		query[i] = { n1 - 1,n2,i };
	}
	divide(0, M - 1);

	int sum = 0;
	int s = query[0].s, e = query[0].e;
	for (int i = s; i < e; i++) sum += arr[i];
	res[query[0].n] = sum;

	for (int i = 1; i < M; i++) {
		while (query[i].s < s) sum += arr[--s];
		while (e < query[i].e) sum += arr[e++];
		while (query[i].s > s) sum -= arr[s++];
		while (e > query[i].e) sum -= arr[--e];
		res[query[i].n] = sum;
	}

	for (int i = 0; i < M; i++) printf("%d\n", res[i]);
}

djm03178 4년 전 0

말씀하신 코드는 모스 알고리즘이 전혀 아닌 것 같은데요. 그러면 최악의 경우 시간 복잡도가 O(NM)이라 시간 초과가 나야 할 것 같은데 오히려 데이터가 약해서 빠르게 통과되는 게 아닌가 싶습니다.

kdr06006 4년 전 0

아 그래요? 죄송합니다

공부를 더 깊이있게 하고 질문을 하겠습니다.

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

문제

문제

출처

ICPC

수행속도 차이가 왜 이렇게 크게나는지 모르겠습니다(모스 알고리즘)

kdr06006 4년 전 0

djm03178 4년 전 0

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말