알고리즘 문제해결전략 책 1권 123페이지에서 이해가 안되는 내용이 있어서 질문합니다.

  • hg9587
    hg9587

    알고리즘 문제해결전략 책 1권 123페이지에서 계산복잡도 이론의 환산(reduction)관련된 설명이 있는데요. 해당 본문에서 이해가 되지 않는 부분이 있어서 질문 올립니다. 내용은 다음과 같은데요

    계산 복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 환산(reduction)이라는 기법을 이용합니다. ...
    <중략>
    환산 알고리즘이 무시할 수 있을 정도로 빠르다고 가정하면 결합된 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같은 시간이 걸릴 겁니다.
    B를 푸는 가장 빠른 알고리즘은 앞에 결합된 알고리즘과 같거나 더 빠를 테니, 결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수 밖에 없습니다.

    밑줄 친 문장 전 까지는 이해가 되었는데, 밑줄 친 문장의 근거는 어디서 나오는지가 궁금합니다.

    (B를 A로 환산하는 알고리즘) + (A를 푸는 알고리즘) = 결합된 알고리즘
    이고

    (B를 A로 환산하는 알고리즘)의 수행시간이 0에 수렴한다고 하면,

    (A를 푸는 알고리즘)의 수행속도와, (결합된 알고리즘)의 수행속도가 같다고 볼 수는 있을 것 같은데, (여기까지가 밑줄 친 문장의 이전 문장의 논리입니다)

    왜 (B를 푸는 가장 빠른 알고리즘)이 (결합된 알고리즘)보다 더 빠를 것인지가 이해가 안됩니다. ㅠㅠ

    제가 이해력이 부족한건가요.. 답변 기다리겠습니다


    2년 전
3개의 댓글이 있습니다.
  • kriii
    kriii

    B를 풀 수 있는 가장 빠른 알고리즘인데 당연히 더 빠른거 아닐까요...


    2년 전 link
  • Unused
    Unused

    (B를 A로 환산하는 알고리즘) + (A를 푸는 알고리즘) = 결합된 알고리즘이고, 이 결합된 알고리즘은 결국 B를 푸는 알고리즘 중 하나이므로 B를 푸는 가장 빠른 알고리즘이 결합된 알고리즘(B를 푸는 알고리즘 중 하나)보다 빠르거나 같을 수밖에 없습니다.


    2년 전 link
  • hg9587
    hg9587

    아 설명을 듣고 곰곰히 생각해보니까 이해가 됩니다! 감사합니다


    2년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.