이진탐색 (1) 썸네일형 리스트형 [자료구조] 정렬 리스트 Array based vs Linked List 정렬 리스트 데이터가 특정 기준으로 정렬되어있는 리스트이다. 예를 들면 정수형 리스트인 경우 오름차순 or 내림차순으로 정렬되어 있다면 정렬리스트이다. 정렬이 되어 있기 때문에 시간복잡도면에서 비정렬 리스트보다 효율적이다. 예를 들어 리스트에서 아이템을 찾아주는 함수의 시간복잡도를 살펴보자면 정렬 리스트가 binary search로 구현된 경우, 시간 복잡도는 O(logN)이지만 비정렬 리스트는 시간 복잡도가 O(N)이다. search 함수 정렬 리스트 (2진 탐색) 비정렬 리스트 시간 복잡도 O(logN) O(N) 정렬리스트를 구현하는 방식도 다양하다. 일단 여기서는 2진 탐색을 기준으로 설명하겠다. Binary Search (2진 탐색) 2진 탐색은 정렬이 된 자료를 반으로 나누어 가며 검색을 하는 .. 이전 1 다음
