위에 건 n^1.5이고 아래 것은 n^2입니다.
1699번 - 제곱수의 합
네 그래서 최악의 경우 n=100000 일때 3배보다 적게 차이 나는데,
제가 이게 얼마나 큰것인지 감이 안잡히니다.
물론 어떤 프로그램이 이러한 로직이 들어가냐에 따라 이 3배가
클 수도 있고 작을 수도 있긴한데
이 문제에서 시간초과가 날정도로 의미있는 시간복잡도 차이인지
아니면 그냥 저 두 경우의 코드(물론 아닐수도있지만)를 구별해서 채점하기 위해
채점결과를 다르게 한 것인지 궁금합니다.
제가 부족해서 질문조차 잘 하지 못하겠네요.
답변 힘드시면 하지 않으셔도 괜찮습니다.
제가 더 공부하겠습니다.
이 문제에서 시간 제한이 2초인데
알고리즘 문제에서 제한 시간이 1초라면 당신의 프로그램은 3-5억 번의 연산 안에 답을 내고 종료되어야 한다는 것을 의미합니다.
그래서 시간복잡도가 안전하게 10^8 정도 나오면 됩니다.
2초도 비슷합니다.
질문 작성자 분의 첫 번째 코드는 시간복잡도가 O(N^1.5)이고, 두 번째 코드는 O(N^2)인데요
N의 최댓값이 10^5라서
첫 번째 코드의 최악의 연산 수 = 10^7.5
두 번째 코드의 최악의 연산 수 = 10^10
따라서 두 번째 코드는 시간 초과가 나올 수밖에 없습니다.
댓글을 작성하려면 로그인해야 합니다.
tldnjs0821 4년 전 1
위 코드와 아래 코드의 시간복잡도가 차이가 많이 나나요?
위의 코드로 했을 때는 정답이 되고, 아래의 코드로 했을 때는 시간초과가 나오네요.
최악의 경우로 계산해봐도 3배 정도 차이나는 거 같습니다.
제가 잘못 계산한 것일 수도 있구요.
제가 잘못 계산한 것인지 아니면 3배도 많이 차이나는 것인지
알려주시면 감사하겠습니다.