kojang   1년 전

마스터 이론으로 한다면 어떻게 하나요 검색해봐도 적용시키는건 어떻게 해야하는지 잘 모르겠네요

jwvg0425   1년 전

top-down DP의 경우, (총 부분 문제의 수) * (각 부분 문제를 해결하는데 걸리는 시간)으로 전체 시간 복잡도를 어림할 수 있습니다.

이 문제의 경우, k 값은 최대가 2고 count값은 최대 n까지 갈 수 있습니다. 즉, 총 부분 문제의 수는 2*n입니다.

각 부분 문제를 해결하는데 걸리는 시간은 메모이제이션을 제외한 함수의 실행 로직 부분의 시간 복잡도라고 생각하시면 됩니다. 이 문제의 경우 단순 계산으로 처리되니 O(1)이겠죠.

따라서 전체 시간복잡도는 O(2*n*1) = O(n)이라고 생각하면 됩니다.

댓글을 작성하려면 로그인해야 합니다.