인프런 커뮤니티 질문&답변
작성한 질문수
시간복잡도 관련
작성
·
267
0
시간복잡도를 2500 * 100 이라고 설명하셨는데,
2500 * 2500 아닌가요?
정점의 최대개수 : 2500
정점마다 bfs 시간복잡도 : 2500 인것 같아서요.
답변 2
0
tastygogi
질문자
답변 감사합니다.
그려주신 그림 기준으로 생각해보면,
LLL
LLL
LLL
가장 먼 정점에 도달하는 비용은 5번이지만
가장 먼 정점을 알아내기 위해서 모든 정점을 방문해봐야 아는 것이니, 그 부분을 시간복잡도(3*3)로 봐야 하는 것이 아닌가 해서요.
0
큰돌
지식공유자
음 정확히 따지면
정점마다 bfs 시간복잡도 : 2500
>> 가 아니라 최악의 경우 2500 / 2 이긴 해요. 맵을 완전히
LLLLLL
WWWWW
LLLLL
이런식으로 나오게 되면 한번 BFS마다 맵의 반정도를 탐색해야하기 때문이죠.
but, 보통의 BFS로 잡으면 100, 50 * 2이가 됩니다. 가로, 세로를 더한 값입니다.
보통 최악 또는 평균값을 기반으로 시간복잡도를 정합니다.
해당부분 설명 추가하겠습니다.
자, 그러면 어떻게 100이냐?
위의 그림이 보통의 맵인데요. 이렇게 보통의 경우 저 마지막 정점, 제일 멀리 있는 정점까지 가는데 5정도밖에 걸리지 않습니다.
가로 세로 더한 값 - 1 인 셈이죠.
그렇기 때문에 50 * 2인 100으로 계산했습니다.
감사합니다.
아 제가 착각했네요 ㄷㄷ
네 맞습니다. 모든 정점 방문해봐야 하니 3 * 3이 맞습니다.
해당부분 수정해서 강의 올리겠습니다.
감사합니다.