jmbook에서 외계 신호 분석 문제에 대해서 질문이 있습니다.. ggabu420 제가 아직 알고리즘에 무지해서 문장이 잘 이해가 안가는 경우가 상당히 많은데.. 외계 신호 분석 문제에 보면 head와 tail 을 이용하는 기법을 설명하고 있는데 여기서 tail 의 최대값이 N 이므로 while 루프는 아무리 해도 N 번 이상 실행되지 않으므로 전체 시간 복잡도는 O(N) 이라고 나와있습니다만... 그런데 while 루프를 보면 사실 for 루프로 감싸여있는데 for( head = 0; head < N; head++ ){ while(~~~){} } 이렇게 되면 while 은 N번이 최대지만 그 루프를 N번 반복하게 되니 결과적으로는 O(N^2) 아닌가요?; 물론 더 정확히 하면 N + (N-1) + (N-2) + (N-3) + ... 가 최악의 경우이니 N(N+1)/2 이고 뭐 어쨌든 이것도 O(N^2) 이고.. 왜 선형 시간인지 잘 이해가 안가네요.. 어딘가 제가 잘못 이해하고 있는 건 분명한데... 11년 전
2개의 댓글이 있습니다. JongMan head가 변해도 tail 값은 그대로 유지되죠. 따라서 for문 내부가 새로 시작할 때마다 while루프가 처음부터 시작되는 것이 아닙니다. n=10이라고 하죠. while문 내부가 10번 실행된다면, 이 10번 수행은 for문 내부가 한번 수행될 때마다 2번, 1번, 0번, 2번.. 식으로 쪼개져서 그 합이 10번이 되는 것이죠. 직접 수행해 보시면서 head와 tail이 어떻게 변하나 한번 확인해 보시면 도움이 되겠습니다. 11년 전 link ggabu420 아 그렇네요!;; 늦은 시간에 빠른 답변 감사합니다'ㅅ'; 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
ggabu420
제가 아직 알고리즘에 무지해서 문장이 잘 이해가 안가는 경우가
상당히 많은데..
외계 신호 분석 문제에 보면
head와 tail 을 이용하는 기법을 설명하고 있는데
여기서 tail 의 최대값이 N 이므로 while 루프는 아무리 해도
N 번 이상 실행되지 않으므로 전체 시간 복잡도는 O(N) 이라고
나와있습니다만...
그런데 while 루프를 보면 사실 for 루프로 감싸여있는데
for( head = 0; head < N; head++ ){
while(~~~){}
}
이렇게 되면 while 은 N번이 최대지만 그 루프를
N번 반복하게 되니 결과적으로는 O(N^2) 아닌가요?;
물론 더 정확히 하면 N + (N-1) + (N-2) + (N-3) + ...
가 최악의 경우이니 N(N+1)/2 이고 뭐 어쨌든 이것도 O(N^2) 이고..
왜 선형 시간인지 잘 이해가 안가네요..
어딘가 제가 잘못 이해하고 있는 건 분명한데...
11년 전