Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/fontdata.js
본문 바로가기

728x90

linked list search

01 문돌이 존버/프로그래밍 스터디 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)의 시간 복잡도를 가집니다. 그렇다면 어떻게 성능을 개선할 수 있을까요? 아래 그림과 같이 각 ..

728x90

티스토리툴바