yjkim997   8달 전

안녕하세요.

제가 계산하기로 시간복잡도가 O(n2)인 코드를 작성했는데, n<=32000인 범위에서도 왜 시간초과가 나지 않는지 궁금합니다. 채점 데이터의 부족인지, 제가 시간복잡도를 잘못 계산한 건지 잘 모르겠습니다.. 

혹시 아시는 분들은 알려주시면 감사하겠습니다.

제출 번호는 103194174입니다. 아래에서도 확인해보실 수 있습니다.

zenith82114   8달 전

C, C++이라면 n이 10만이 안 되면 O(n^2)이 충분히 돌 수 있습니다. 심지어 n=10만이어도 O(n^2) 알고리즘이 도는 경우도 드물지 않습니다.

yjkim997   8달 전

@zenith82114
그렇군요.. 친절히 알려주셔서 감사합니다. 하나만 더 질문드려도 괜찮을까요?


이런 상황에서는 프로그램 실행시간을 대략적으로 어떻게 계산하면 좋을까요?

저는 단순히 for문이 1억 번 돌아가면 1초가 소요된다고 생각을 했고, 제 코드는 최대 320002번 돌아갈 수 있으니 시간 초과가 날 것이라고 생각을 했었습니다.

그냥 이런 상황이 예외적인 것이라고 생각하고 넘어가는 것이 좋을지, 아니면 다른 n<10만 인 상황에서도 O(n^2)이 돌 것이라고 생각하고 코드를 짜는 것이 좋을지 잘 모르겠습니다.

zenith82114   8달 전

시간 예측은 단순히 for문 횟수만 세서 할 수 있는 일은 아니고, 많이 반복하고 있는 연산이 무거운지 가벼운지도 살펴봐야 합니다.

지금 코드에서는 O(n^2)번 하게 되는 일이 indegree 배열 읽기와 if 조건 검사로 이들은 매우 가벼운 연산입니다. 정확히는 32000^2가 아닌 1+2+...+32000 ~= 5e8 정도로, 시간제한 1초면 웬만하면 가능하다고 보는 수치입니다. 하지만 std::set에 삽입/삭제를 10^9번 하는 코드가 1초에 돌아가기는 더 어렵다고 예상할 수 있습니다. 어떤 작업이 1초에 몇 번까지 가능한지는 주로 경험을 통해 감이 쌓이게 되고 CS 지식이 있으면 다소 도움이 됩니다.

aiden3233   8달 전

이 문제 데이터가 부족한것도 있는 것 같습니다. https://www.acmicpc.net/board/... 여기에 데이터 추가 요청을 올렸습니다.

zenith82114   8달 전

@aiden3233 말씀하신 데이터도 위의 코드로 제 로컬에서 128ms만에 돌아갑니다. 채점 서버 기준으로도 1초가 걸리지 않을 거라 생각합니다.

aiden3233   8달 전

생각보다 제곱이 빨리 도는군요... 감사합니다.

yjkim997   8달 전

감사합니다!

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