파이썬 자료구조 (2) 썸네일형 리스트형 우선순위 큐 (priority queue), 힙 정렬 (heap sort) 우선순위 큐 (priority queue)- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다.- 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다. 배열을 사용하는 방법 1. 정렬이 안 되어 있는 배열의 경우삽입 시간 복잡도 \(O(1)\)삭제 시간 복잡도 \(O(n)\) 2. 정렬이 되어 있는 배열의 경우삽입 시간 복잡도 \(O(n)\)삭제 시간 복잡도 \(O(1)\) 연결 리스트를 사용하는 방법 1. 정렬이 안된 리스트- 삽입 시에 첫번째 노드로 삽입시키는 것이 유리하다. 다른 노드를 이동할 필요가 없다. 포인터만 변경하면 된다. 삽입 시간 복잡도 \(O(1)\)- 삭제 시에 포인터를 따라서 모든 노드를 뒤져보아야 한다. 삭제.. 정렬 알고리즘 (sorting algorithm) 정리 순차탐색(sequential search)- 시간복잡도 : O(n)- 데이터가 정렬되어 있지 않아도 사용할 수 있다. 이진탐색(binary search)- 시간복잡도 : O(logn)- 데이터가 순서에 맞게 정렬되어 있어야 한다. 알고리즘 Best Average Worst Stable Memory 버블 정렬 (n^2) (n^2) (n^2) True 선택 정렬 (n^2) (n^2) (n^2) False 삽입 정렬 (n) (n^2) (n^2) True 셸 정렬 (nlog_2n) (n^{1.5}) (n^2\) False 퀵 정렬 (nlog_2n) (nlog_2n) (n^2\) False 히프 정렬 (nlog_2n) (nlog_2n) (nlog_2n) False 합병정렬 (nlog_2n) (nlog_2n) (n.. 이전 1 다음
