amatuer789   5년 전

이 문제와 같이, DFS에서

visited 를 해제 및 적용하는 알고리즘에서는 

시간 복잡도 계산을 어떻게 하나요???

chogahui05   5년 전

4 * 3^(n-1) 정도 되겠네요. 사실 4^n은 아닙니다.

4 * 3^13 = 대략 600만이므로, 시간 내에 들어옵니다. 왜 뒤에 4의 x승이 아니라 3의 x승이 붙냐면. 왔던 길을 다시 되돌아 가는 경우는 제외해야 하기 때문입니다.

또한 실제로, 가지가 쳐지는 경우는 생각보다 꽤 있기 때문에, 4 * 3^13보다는 적을 듯 싶네요.

amatuer789   5년 전

4 --> 3 으로 1 만 감소해도, 전체 복잡도가 많이 떨어지는군요.

빠른 답변 감사드립니다.

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