| [ QuizWit ] in KIDS 글 쓴 이(By): guest (tototo) 날 짜 (Date): 1998년 4월 16일 목요일 오전 07시 12분 07초 제 목(Title): [답] 위의 알고리듬에 대해 O(1) 가 나오는경우는 exact solution이 존재하는경우이지요. ^^ knap sack problem의 경우는 fractitonal 이라해도 O(n) 입니다. 그런데 이건 솔직히 이문제에 대해 제대로 이해를 못한경우이지요. 냅삭문제에서 쓰이는 그리드 알고리듬자체는 O(n)이지만 님께서 위에 포스팅한 문제는 exact solution이 존재하는 문제입니다. 그리고 exact solution은 mathematical expression으로 closed form으로 표현이 가능합니다. 문제는 문제의 스트럭쳐에서 볼수있듯이 solution x_j는 x_(j-1),... x_(1)에 의해 정의되어지는 inductive algorithm 입니다. 물론 제가 위에서 말한 특수한 경우 (즉 a_(j-1) | a_j ) 를 제외하고는 해가 많습니다. 하지만 해가 많다고해도 finite하고 이론적으로 이문제는 O(1) 입니다. 흔히들 greedy알고리듬이라 부릅니다. 그리드 알고리듬이란건 사실 별게 아닙니다. 여기에 대해서는 상당히 많은 variation이 존재하는데 기억이 안나는데 스프링어 벌락에서 몇년전에 출판한 computation알고리듬 책에 여기에 대한 완벽한 수학적 분석을 해놓았습니다. 혹시 책제목아시는분! (노란색에 까만점 있는 씨리즈중하나였습니다. O(1) 이냐 O(n)이냐 하는건 관점의 차이죠. 러닝타임을 정확히 어떻게 정의 했냐는것입니다. 여기선 n개의 x_1, ... x_n을 구하는것이니까 당연히 미니멈 O(n)인데 running time = computational running time + algorithmic search running time 입니다. 만약 저의 주장을 buy하신다면 알고리드믹 서치의 러닝타임은 O(1) 이지만 각각의 해에 대해 컴퓨테이션을 해야하니 O(n) + O(1) = O(n) 입니다. 그런데 크크... 정통적 방식의 그리디 서치 알고리듬으로할경우 computational running time = O(1) 인 반면 알고리드믹 서치가 O(n)먹힙니다. 결국 이경우에도 O(1) + O(n) = O(n)이죠. 님께서 포스팅한 문제는 소위 컴비네토릭스 (크누뜨 책 참조할것) 에 흔히 나오는 coin exchange problem하고 동치인 문제입니다. 물론 트렌스폼을 해야하지만... 유명한 MIT에서 나온 introduction to algorithms는 그리디 알고리듬쪽이 빈약합니다. 빈약한게 아니라 저자의 무지를 드러낸다고 보면 됩니다. 그리디 본격적으로 할려면 erdos의 수학논문을 봐야할껍니다. |