글 읽기 - 시간 복잡도가 궁금합니다

jdw7645 2년 전 1

1부터 진행한 광년 수까지의 합과 비교해서 다음 이동할 광년을 구하는 식으로 작성했습니다.

일단 답은 맞았는데 인터넷으로 풀이를 보니 반복문을 사용하면 시간 초과가 발생한다고 하더라고요

그래서 왜 시간 초과가 발생하지 않았는지도 궁금하고 아직 시간복잡도에 익숙해지지 않아서 계산이 쉽지 않은데 설명좀 부탁드립니다!

#include <iostream>

using namespace std;

int alpha_centauri(int distance) {
	int count = 0;
	int go = 1;
	int temp;
	while (distance != 0) {
		distance -= go;
		temp = (go * (go + 1) / 2);
		if (distance > temp) {
			if (distance - go < temp) {
				go--;
			}
			else {
				go++;
				temp = (go * (go + 1) / 2);
				if (distance < temp) {
					go--;
				}
			}
		}
		else if (distance == temp) {
			
		}
		else {
			go--;
		}
		count++;
	}
	return count;
}

int main() {
	cin.tie(0);
	int T, x, y;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> x >> y;
		cout << alpha_centauri(y - x) << "\n";
	}
}

bamgoesn 2년 전 2

근본적인 분석은 차치하고 해당 코드에서 시간복잡도를 빠르게 판별할 수 있는 예시만 보여드리겠습니다.

우주선이 속도 go까지 가속했다가 점점 감속하면서 비행을 완료했을 때, 우주선이 이동한 거리는 대체로 go에 대한 2차 함수 비슷하게 나올 겁니다. 여기서 count는 대체로 go의 2배쯤 될 테니, 우주선이 이동한 거리는 count에 대한 2차 함수 비슷하게 될 겁니다. 즉, count는 우주선이 이동한 거리의 제곱근 정도가 됩니다. (O(sqrt(count)))

alpha_centauri 함수에서, 루프문은 while (distance!=0) 하나뿐입니다. 이 루프 안에는 다른 루프문이 없으므로 하나의 루프가 시행되는 데에는 대체로 상수시간이 소요되며, 하나의 루프가 끝날 때마다 count가 하나씩 증가합니다. 즉, 해당 루프문은 count회 실행됩니다.

앞서 count는 우주선 이동거리, 즉 y-x에 대해 대략 제곱근이라고 했습니다. 즉, 이 코드의 시간복잡도는 O(sqrt(y-x))가 됩니다. 시간초과가 나지 않는 시간복잡도입니다.

jdw7645 2년 전 0

자세한 설명 감사합니다!! 다른 질문에서 간단하게 O(sqrt(y-x))라길래 왜인지 이해가 전혀 안갔는데 확실히 이해갔습니다!!!

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

문제

문제

출처

ICPC

시간 복잡도가 궁금합니다

jdw7645 2년 전 1

bamgoesn 2년 전 2

jdw7645 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말