stiti   2년 전

n*n배열에서 stl의 queue를 이용하여 bfs를 할 경우 시간복잡도가 궁금합니다.


n*n크기의 맵을 모두 탐색하므로 N^2인지 아니면 STL의 queue를 사용하면서 시간복잡도가 더 증가하는 것인지 궁금합니다.

chogahui05   2년 전

최악의 경우 맵 크기로 알고 있는데요.. 

stl의 queue를 사용한다고 시간 복잡도가 증가하진 않습니다.


보통 Queue 같은 경우, pop 연산과 push 연산을 많이 쓰는데요.

이 함수들은 O(1)에 동작합니다.

stiti   2년 전

답변 감사합니다 :)

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