Time Complexity of DFS

인공지능시스템 수업 녹화강의를 보다가 궁금한 점이 생겨 알아본 내용이다

 

교수님께서 DFS 알고리즘의 시간 복잡도가 O(b^d)라고 말씀하셨는데

기존에 알고있던, 그리고 저번 학기 "자료구조 및 알고리즘" 수업에서 같은 교수님께서 말씀하신 O(V+E)가 아니길래

궁금해져서 찾아봤다

정말 단순히 '어라 원래 저렇게 생겼나?' 싶어서였다. 깊은 고민을 하진 않았다

 

- b: number of child node

- d: maximum depth

- V: number of node

- E: number of edge

 

stackoverflow에서 만족할만한 답변을 얻었는데, 요약하자면 다음과 같다

트리의 총 노드 수의 최대값은 1 + b + b^2 + ... + b^(d-1)로, 각 항은 각 레벨에서의 노드 수가 된다

이 식은 등비수열로 그 합은 (b^d -1) / (b-1) 공식으로 계산된다

이 식을 단순화 하면 b^d가 되고

최악의 시간복잡도는 O(b^d)가 된다

이러한 방법 대신 트리의 총 노드 수를 알고 있다면 시간복잡도를 직접 O(n)으로 표현할 수 있다

더 정확한 복잡도 계산을 위해 엣지 수를 고려할 수도 있지만 복잡도 분석에서는 일반적으로 노드의 수에 초점을 맞추는 것으로도 충분하다

 

결국 DFS 알고리즘의 시간복잡도 계산에 있어서 가장 중요한 것은 노드의 수이며,

O(b^d) 역시 주어진 조건 아래에서 트리의 총 노드 수를 계산하기 위한 방식이 적용된 시간복잡도임을 알 수 있었다

 

재밌다 그래도 조금만 더 생각해볼걸!

아래 링크를 참고 부탁드립니다

 

https://stackoverflow.com/questions/36479640/time-space-complexity-of-depth-first-search

Time/Space Complexity of Depth First Search