[질문] 탑 다운 동적계획법의 시간복잡도 분석을 어떻게...

[익명(59.31)]

바텀 업 방식으로 구현하면 한가지의 입력에 대해 연산 횟수를 파악하기 쉽고 총 시간복잡도를 분석하기 쉬운 것 같은데

탑다운 방식으로 하면 명쾌한 이해가 떠오르지 않아 답답하네요...

[하루룽(ailedear)]

dp배열이 [V][V]이고 함수 한번 실행될때마다 O(E)면 배열 다채우는데 O(V^2E) 이런식으로?

[Nagne(sunjongyun)]

흐 덕분에 배워갑니다

[시아닌(kimjg1119)]

상태공간 개수 * 함수 한번당 시간인데 amortized면 따로 계산해줘야됨