jmbook에서 외계 신호 분석 문제에 대해서 질문이 있습니다..

  • ggabu420
    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) 이고..

    왜 선형 시간인지 잘 이해가 안가네요..


    어딘가 제가 잘못 이해하고 있는 건 분명한데...


    5년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    head가 변해도 tail 값은 그대로 유지되죠. 따라서 for문 내부가 새로 시작할 때마다 while루프가 처음부터 시작되는 것이 아닙니다. n=10이라고 하죠. while문 내부가 10번 실행된다면, 이 10번 수행은 for문 내부가 한번 수행될 때마다 2번, 1번, 0번, 2번.. 식으로 쪼개져서 그 합이 10번이 되는 것이죠.

    직접 수행해 보시면서 head와 tail이 어떻게 변하나 한번 확인해 보시면 도움이 되겠습니다.


    5년 전 link
  • ggabu420
    ggabu420

    아 그렇네요!;; 늦은 시간에 빠른 답변 감사합니다'ㅅ';


    5년 전 link
  • 댓글을 남기시려면 로그인하세요.