알고리즘 문제해결 책 250 페이지 wraith7 quantize 시간복잡도가 O(n^2s)라고 나와있는데요. n개의 숫자를 s개의 그룹으로 나누는 총 경우의 수가 이미 (n-1)C(s-1)이 아닌가요?(여기서 C는 combination입니다.) 책에서 사용한 알고리즘은 n개의 숫자를 s개의 그룹으로 나누는 모든 경우를 다 탐색하는 알고리즘이므로 시간복잡도는 O(n-1 C s-1)이 되는게 아닐까 싶습니다. 8년 전
2개의 댓글이 있습니다. JongMan 모든 경우를 다 탐색한다고 해서 그만큼의 시간이 걸리는 것은 아닙니다. 중간 과정에서 중복되는 계산은 반복하지 않고 저장해 둔 값을 이용해 시간을 줄일 수 있죠. (이것이 동적 계획법의 기본 원리입니다) 8년 전 link wraith7 음.. 아 제가 너무 어이없게 잘못 생각했네요;;; 답변 감사드립니다. 부분문제가 한번 계산된 이후에 더 작은 부분문제로 쪼갤 필요가 없었는데, 쪼개도록 계산을 해버렸네요. 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
wraith7
quantize 시간복잡도가 O(n^2s)라고 나와있는데요.
n개의 숫자를 s개의 그룹으로 나누는 총 경우의 수가 이미 (n-1)C(s-1)이 아닌가요?(여기서 C는 combination입니다.)
책에서 사용한 알고리즘은 n개의 숫자를 s개의 그룹으로 나누는 모든 경우를 다 탐색하는 알고리즘이므로 시간복잡도는 O(n-1 C s-1)이 되는게 아닐까 싶습니다.
8년 전