인프런 커뮤니티 질문&답변
작성한 질문수
답변 1
0
안녕하세요. harry님ㅎㅎ
저거 보시면 for문이 2개로 중첩되어 있죠?
for i ~ n
for j ~ n
따라서 O(n^2)입니다.
이것말고도 sort니 뭐니 하는게 있긴 하지만 제일 "큰 거" 선택하시면 됩니다.
sort는 O(nlogn)이구요.
if(m == ) return 하는 것은 O(1)입니다.
이중에서 가장큰 것은 뭘까요?
중첩for문이죠?
따라서 시간복잡도가 O(n^2)이 됩니다.
또 질문사항있으시면 언제든 말씀 부탁드립니다.
감사합니다.
강사 큰돌 올림.
정확히는
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
이기 때문에 1 / 2 * n^2입니다. 여기서 이를 빅오표기법으로 나타내면 n^2이구요. 약 112,500,000 정도의 시간복잡도를 가진다고 생각하면 되는데요. 약 1억이죠. 근데 여기서
고유한 번호는 100,000보다 작거나 같은 자연수이다.
라는 문제 조건이 있죠. 그렇기 때문에 m이 만약 20만을 넘어가게 되면 예외처리를 하는것이죠. 2개를 골라서 20만을 넘을 수는 없기 때문에. 어림잡아 1억이라는 시간복잡도가 나오지만 저 예외상황 때문에 좀 더 작게 계산되서 1억보다는 실제로는 더 작은 시간복잡도를 가질 수 있습니다.
또한 이 문제의 시간제한은 2초입니다. 보통은 1억이 통과가 안되지만 이 문제는 넉넉한 시간제한으로 통과할 수도 있는 셈이죠.
즉, 이렇게 이해하시면 됩니다.
"예외상황 때문에 실제로는 시간복잡도가 1억미만일 수도 있으며 문제마다 시간제한이 달라 1억짜리가 통과할 수도 있다. 하지만 보통은 1억짜리 시간복잡도가 통과를 하지 못한다."
또 질문사항있으시면 언제든 말씀 부탁드립니다.
감사합니다.
강사 큰돌 올림.
답변 감사합니다. 추가로 궁금한 점 문의드립니다.
보통 시간복잡도 크기가 100,000,000이 넘어가면 시간초과가 발생하는 것으로 알고있는데요!
해당 풀이의 경우 시간복잡도가 O(N^2)이고, 입력값 N이 최대 15,000이니까 다음과 같은 시간복잡도를 가질텐데,
15,000 x 15,000 = 225,000,000
왜 시간초과가 발생하지 않고 통과가 되는 것인지 궁금합니다!