hyun353   2년 전

15686 치킨배달 문제에서 DFS를 이용한 완전탐색에 관한 시간복잡도 질문이 있어 연락드렸습니다.

현재 아래 코드에서 47~61번 줄에 관한 질문입니다.

처음에 55~61번줄 같이 for문 시작을 0에서 부터 시작하도록 설계 하였습니다. 하지만 이와 같이 설계를 하니 시간초과가 나타났습니다.

그 후 47~53번줄과 같이 for문 시작을 start라는 변수를 통해 시작하도록 하니 시간초과가 나타나지 않았습니다. 

혼자 그 이유를 추측해보았는데 for문 시작을 0에서 부터 시작하게되면 최악의 경우 O(13^13)과 같은 시간복잡도가 나오는것 같다 추측하였습니다.

그렇다면 47~53번줄과 같이 코딩하였다면 어느정도의 시간복잡도가 나오는지 추측이 되질 않습니다.


답변해주시면 감사하겠습니다. 

djm03178   2년 전

start번째부터 시작하게 되면 결과적으로 최대 13개의 치킨집에서 최대 13개를 고르는 것과 같습니다. 이 중에서 최악은 13C6으로 1716이고, 여기에 정확히는 모르겠지만 함수 호출 횟수로 O(N) 정도가 더 붙지 않을까 싶네요.

hyun353   2년 전

그렇다면 처음에 제가 설계했던 부분은 O(13^13)의 시간복잡도를 가지는 것은 맞나요?

djm03178   2년 전

그것보단 작은 것 같습니다. O((n+1)!) 이 아닌가 싶네요.

hyun353   2년 전

아 정말 감사합니다!!! 도움이 정말 많이됬어요!!

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