Inflearn Community Q&A
asked
시간복잡도에 대하여..
Written on
·
428
0
BFS 알고리즘을 배우고 난뒤 시간복잡도에 대해 생각이 많아집니다.
BFS알고리즘의 시간복잡도는 O(N^2)인데
사진을 보시면 O(N^2) 부터는 Horrible 단계이므로 사용을 별로 권장하지 않는 것 처럼 보이는데 O(N^2)까지는 어쩔수 없이 종종 사용하게 되는걸까요? (2^n 까지만 가지 않는다면 괜찮은걸까요?!)
C#
Answer 2
0
Rookiss
Instructor
저건 정말 최최최악의 상황이고,
실제로 그래프는 연결된 간선이 N까진 가지 않습니다.
(지하철 노선도를 생각하면, 한 역이랑 연결된 역이 양옆으로 2개 정도가 일반적이겠죠!)
0
이해했습니다 감사합니다!