tldnjs0821   4년 전

위 코드와 아래 코드의 시간복잡도가 차이가 많이 나나요?

위의 코드로 했을 때는 정답이 되고, 아래의 코드로 했을 때는 시간초과가 나오네요.

최악의 경우로 계산해봐도 3배 정도 차이나는 거 같습니다.

제가 잘못 계산한 것일 수도 있구요.

제가 잘못 계산한 것인지 아니면 3배도 많이 차이나는 것인지

알려주시면 감사하겠습니다.

gs18103   4년 전

위에 건 n^1.5이고 아래 것은 n^2입니다.

tldnjs0821   4년 전

네 그래서 최악의 경우 n=100000 일때 3배보다 적게 차이 나는데,

제가 이게 얼마나 큰것인지 감이 안잡히니다.

물론 어떤 프로그램이 이러한 로직이 들어가냐에 따라 이 3배가

클 수도 있고 작을 수도 있긴한데

이 문제에서 시간초과가 날정도로 의미있는 시간복잡도 차이인지

아니면 그냥 저 두 경우의 코드(물론 아닐수도있지만)를 구별해서 채점하기 위해

채점결과를 다르게 한 것인지 궁금합니다.

제가 부족해서 질문조차 잘 하지 못하겠네요.

답변 힘드시면 하지 않으셔도 괜찮습니다.

제가 더 공부하겠습니다.

namu1092   4년 전

이 문제에서 시간 제한이 2초인데

알고리즘 문제에서 제한 시간이 1초라면 당신의 프로그램은 3-5억 번의 연산 안에 답을 내고 종료되어야 한다는 것을 의미합니다.

그래서 시간복잡도가 안전하게 10^8 정도 나오면 됩니다.

2초도 비슷합니다.

질문 작성자 분의 첫 번째 코드는 시간복잡도가 O(N^1.5)이고, 두 번째 코드는 O(N^2)인데요

N의 최댓값이 10^5라서

첫 번째 코드의 최악의 연산 수 = 10^7.5

두 번째 코드의 최악의 연산 수 = 10^10


따라서 두 번째 코드는 시간 초과가 나올 수밖에 없습니다.

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