quki   1년 전

외판원 순회문제를 DP + 비트마스크로 풀었습니다.

이차원 배열 dp[i][visited] 를 잡고 i정점에서 지나온 경로가 visited(비트) 일때 최단 경로 값을 Top-down 방식으로 배열에 메모이제이션해주고 있습니다.

이때 시간 복잡도가 어떻게 나오는지 궁금합니다.

제 생각에는  dp 이차원 배열에서 전체 칸 수 x 한칸을 채우는 복잡도 = n*2^n x n(???????) = n^2*2^n 인 것 같은데 맞나요?

이차원 배열 전체를 채우는 복잡도는 알겠는데 한칸을 채우는 복잡도가 n이 맞는지 궁금합니다. 

hihihi   1년 전

O(n^2*2^n) 맞습니당

quki   1년 전

감사합니당!^^

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