글 읽기 - 시간초과 원인

rnjstpgns91 6년 전 0

시간초과 원인을 모르겠습니다. cin, cout 문제인지 알고 printf나 scanf로 해보아도 똑같이 시간초과가 발생합니다.

#include <iostream>
#include <stdio.h>
using namespace std;

#define size 100000

int A[size], B[size];

int BT(int arr[], int low, int high, int target);
void B_S(int arr[], int n);
void QS(int A[], int x, int y);


int main()
{
	int N, M;

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	QS(A, 0, N - 1);

	cin >> M;

	for (int j = 0; j < M; j++)
	{
		cin >> B[j];
	}

	for (int k = 0; k < N; k++)
	{
		int t;

		t = BT(A, 0, N-1, B[k]);
		printf("%d \n", t);
	}

	return 0;

}

int BT(int arr[], int low, int high, int target)
{
	int mid;

	mid = (low + high) / 2;

	if (low > high) return 0;

	if (target < arr[mid]) BT(arr, low, mid - 1, target);
	else if (target > arr[mid]) BT(arr, mid + 1, high, target);
	else return 1;
}

void QS(int A[], int x, int y)
{
	if (x >= y) return;

	int p, l, r, temp;
	p = x;
	l = x + 1;
	r = y;

	while (l <= r)
	{
		while (l <= r && A[l] < A[p])
		{
			l++;
		}

		while (l <= r && A[r] > A[p])
		{
			r--;
		}

		if (l < r)
		{
			temp = A[l];
			A[l] = A[r];
			A[r] = temp;
		}

		temp = A[r];
		A[r] = A[p];
		A[p] = temp;

		QS(A, x, y - 1);
		QS(A, y+1, y);
	}
}

bupjae 6년 전 1

quicksort 에서 pivot 를 항상 배열의 맨 처음으로 결정하고 있습니다.

이미 정렬된 배열이 입력으로 들어올 경우 이 quicksort 의 수행 시간은 O(n^2) 이 되어서 시간초과가 나옵니다.

jh05013 6년 전 1

https://www.acmicpc.net/blog/v...
"퀵소트를 직접 구현했을 때, pivot을 처음 값, 끝 값 등 간단하게 잡으면 최악의 경우인 O(N^2)이 걸리는 데이터를 손쉽게 만들 수 있습니다. 그냥 내장된 정렬 함수를 쓰세요."

rnjstpgns91 6년 전 0

댓글 모두 감사합니다!!

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

문제

문제

출처

ICPC

시간초과 원인

rnjstpgns91 6년 전 0

bupjae 6년 전 1

jh05013 6년 전 1

rnjstpgns91 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말