알고리즘 문제해결전략 책 1권 123페이지에서 계산복잡도 이론의 환산(reduction)관련된 설명이 있는데요. 해당 본문에서 이해가 되지 않는 부분이 있어서 질문 올립니다. 내용은 다음과 같은데요
계산 복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 환산(reduction)이라는 기법을 이용합니다. ...
<중략>
환산 알고리즘이 무시할 수 있을 정도로 빠르다고 가정하면 결합된 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같은 시간이 걸릴 겁니다. B를 푸는 가장 빠른 알고리즘은 앞에 결합된 알고리즘과 같거나 더 빠를 테니, 결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수 밖에 없습니다.
밑줄 친 문장 전 까지는 이해가 되었는데, 밑줄 친 문장의 근거는 어디서 나오는지가 궁금합니다.
(B를 A로 환산하는 알고리즘) + (A를 푸는 알고리즘) = 결합된 알고리즘
이고
(B를 A로 환산하는 알고리즘)의 수행시간이 0에 수렴한다고 하면,
(A를 푸는 알고리즘)의 수행속도와, (결합된 알고리즘)의 수행속도가 같다고 볼 수는 있을 것 같은데, (여기까지가 밑줄 친 문장의 이전 문장의 논리입니다)
왜 (B를 푸는 가장 빠른 알고리즘)이 (결합된 알고리즘)보다 더 빠를 것인지가 이해가 안됩니다. ㅠㅠ
hg9587
알고리즘 문제해결전략 책 1권 123페이지에서 계산복잡도 이론의 환산(reduction)관련된 설명이 있는데요. 해당 본문에서 이해가 되지 않는 부분이 있어서 질문 올립니다. 내용은 다음과 같은데요
계산 복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 환산(reduction)이라는 기법을 이용합니다. ...
<중략>
환산 알고리즘이 무시할 수 있을 정도로 빠르다고 가정하면 결합된 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같은 시간이 걸릴 겁니다.
B를 푸는 가장 빠른 알고리즘은 앞에 결합된 알고리즘과 같거나 더 빠를 테니, 결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수 밖에 없습니다.
밑줄 친 문장 전 까지는 이해가 되었는데, 밑줄 친 문장의 근거는 어디서 나오는지가 궁금합니다.
(B를 A로 환산하는 알고리즘) + (A를 푸는 알고리즘) = 결합된 알고리즘
이고
(B를 A로 환산하는 알고리즘)의 수행시간이 0에 수렴한다고 하면,
(A를 푸는 알고리즘)의 수행속도와, (결합된 알고리즘)의 수행속도가 같다고 볼 수는 있을 것 같은데, (여기까지가 밑줄 친 문장의 이전 문장의 논리입니다)
왜 (B를 푸는 가장 빠른 알고리즘)이 (결합된 알고리즘)보다 더 빠를 것인지가 이해가 안됩니다. ㅠㅠ
제가 이해력이 부족한건가요.. 답변 기다리겠습니다
7년 전