문돌이 존버/프로그래밍 스터디
2021. 2. 9.
Binary Search Tree, 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (8)
지금까지 Linked list 및 해시 테이블까지 살펴봤습니다. Linked list는 첫 노드만 알고 있으면 해당 리스트 내 모든 노드값들을 알 수 있습니다. the value of first node = 1 first.next.val = 2 first.next.next.val = 3 그런데 Linked list는 search 방면에서 시간 복잡도가 무조건 $O(N)$이 걸리기 때문에 7을 찾기 위해선 전체 리스트를 쭉 훑어야 합니다. 이보다 조금 나은 성능을 보이는 것은 아래와 같이 first 노드를 기준으로 한 번은 왼쪽, 한 번은 오른쪽에 노드를 연결하는 것인데요. 이 역시 $O(N/2)$, 즉 O(N)의 시간 복잡도를 가집니다. 그렇다면 어떻게 성능을 개선할 수 있을까요? 아래 그림과 같이 각 ..
