패스트 캠퍼스 챌린지 20일차 - 자료구조 트리#6

목차

1. BST 시간 복잡도

1.BST의 시간복잡도

• depth (트리의 높이) 를 h라고 표기한다면, O(h)
• n개의 노드를 가진다면, h=log2n 에 가까우므로, 시간 복잡도는 O(logn)
  • 참고: 빅오 표기법에서 logn 에서의 log의 밑은 10이 아니라, 2입니다.
    • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

      

      (출처:  https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node )

 

https://bit.ly/37BpXiC