rhtkdwls   6년 전

안녕하세요!

Mo's Algorithm을 이용해 문제 14413을 풀었습니다. 다만, 알고리즘 시간 복잡도를 계산할 때 궁금한 점이 있습니다.

Mo's Algorithm의 구간의 길이가 N, 쿼리의 갯수가 Q라고 할 때, 알고리즘의 시간복잡도는

O((N + Q) * sqrt(N) + N) 이라고 알고있습니다. 

(출처 : http://www.secmem.org/blog/2019/02/09/mo's-algorithm/)

그런데 이 문제에서 N = 500,000 이고 Q = 500,000 인 상황에서 위 식의 값은

1,000,000 * 707 + 500,000 = 약 7억

입니다.

제한시간이 "5초"인이 문제에서 저는 "값 압축"까지 했는데, 왜 시간초과가 안나왔는지 모르겠습니다.

사실, "1초에 1억번 연산"과 같은 주먹구구식 계산이 항상 정확하지는 않다고도 알고 있습니다. 

(출처 : https://book.algospot.com/estimation.html)

그렇다면, 자신이 머릿속에 그린 알고리즘이 제한 시간 안에 풀릴 지 어떻게 알 수 있을까요?

감사합니다.

rhtkdwls   6년 전

알고리즘 대회에서 문제를 만들 때, 시간 제한이나 변수의 크기를 정하는 과정에서 어떤 기준으로 정할까요? 그것도 궁금하네요

djm03178   6년 전

꼼꼼하게 준비하는 대회라면 여러 테스트를 거쳐서 제한들을 설정합니다. 출제자의 풀이뿐만 아니라 검수진들이 각자 풀이를 짜보고, 출제자가 의도한 방향의 풀이라면 웬만하면 여유있게 통과될 수 있으면서도 의도하지 않은 비효율적인 풀이는 충분히 차단할 수 있는 제한을 설정하기 위해 이리 저리 설정을 바꾸어가면서 적절한 제한을 찾습니다.

djm03178   6년 전

또한 저는 개인적으로 1초에 3억보다도, 간단한 연산이 1초에 20억개 정도가 가능하다는 것부터 시작해서 역으로 "1 단위에 몇 개의 복잡한 연산이 필요한가"를 대충 계산해서 속도를 줄여나가는 쪽으로 생각합니다.

rhtkdwls   6년 전

댓글 달아주셔서 감사합니다!

"1 단위에 몇 개의 복잡한 연산이 필요한가"에서 속도를 줄여나가는 쪽으로 생각한다는 것은 무엇인지 여쭤봐도 되나요???

djm03178   6년 전

다음 두 코드 중에 어느 것이 더 오래 걸릴지 생각해 보세요.

rhtkdwls   6년 전

무슨 말씀인지 알겠습니다!

감사합니다!!

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