junyoung292   7년 전

위에 큐 문제와 크게 다른것은 없지만

한가지 질문이 있어서 올립니다

아래 코드를 보시면 int point를 선언하여 원형큐를 사용하여 풀었습니다.

근데 여기서 원형큐의 위치를 나타내는 point를 int 형이 아닌 long int 로 선언하였을경우

시간초과가 뜨는것을 확인하였습니다.

시간초과가 나는 이유를 도무지 모르겠어서 질문드립니다.

pichulia   7년 전

띠용. 시간초과가 안나는게 이상한데요..ㄷㄷ

junyoung292   7년 전

자세히 설명해주실 수 있나요??

메모리문제라면 이해가 가는데 시간복잡도하고는 무슨 관계가 있는지 이해가 잘 가지 않습니다ㅠ

pichulia   7년 전

현재 코드의 시간복잡도는 O(NM * H(M)) , H(M)은 harmonic 수열의 M번째 값 입니다. 대충 O(NM log M) 정도인데..

이런 생각보다 별로 크진 않았군요.;;


저렇게 풀어도 N = 5000, M = 5000인 경우에 대해 답이 2초안에 나온다는게 신기했습니다.ㄷㄷ

junyoung292   7년 전

입력값이 크지 않아서 시간초과는 안날것 같다 판단했습니다.

근데 제가 질문드린것은 이해가 아직 안갑니다.

int 형을 사용했을경우 시간초과가 나지 않는데 long int를 사용한것은 왜 시간초과가 날까요?

pichulia   7년 전

32bit 데이터의 덧셈/곱셈/나눗셈 에 드는 시간과

64bit 데이터의 덧셈/곱셈/나눗셈 에 드는 시간을 비교해보면

당연히 64bit 데이터에 대한 연산시간이 더 크겠죠.



특히나 나눗셈(/)과 나머지(%)연산의 경우 다른 연산자보다 더더욱 많은 계산시간을 요구하기로 유명한 연산자입니다.

아무리그래도 수행시간이 2배씩이나 차이가 나지 않는 것이 보통이지만,

point%N 때문에 int형에 비해 long int가 2배의 시간을 잡아먹은 것으로 보입니다.

if(Arr[point%N]==0)

이 연산은 한칸 움직일 때마다 항상 호출되는 구문니까요..

junyoung292   7년 전

어렴풋이 생각하던건데 정리가 안되고 있었습니다.

정확히 정리해주셔서 감사합니다.


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