자료구조
-
[ 선형 자료구조 ] 연결 리스트 - Singly linked list(단순 연결 리스트)Computer Science/자료 구조 2022. 12. 28. 19:17
연결 리스트는 각각의 요소들이 "노드"에 저장되는 선형 자료 구조이다. 각 노드들은 다음 노드에 대한 참조값을 가지며 이를 "링크"라 한다. 이러한 노드들로 이루어진 연결 리스트는 노드의 link filed를 사용함으로써 데이터의 추가 및 삭제를 모든 리스트 인덱스에 대한 방문 및 재구성 없이 실행 가능하다. 연결 리스트는 스택, 큐, 그래프 등을 구현하는데 자주 사용되며, 그 종류로는 Singly linked list, Doubly linked list 등이 있다. 1. 기본 배경 지식 1) Node 연결 리스트를 구성하는 노드는 Data filed, Linke filed 두 가지 필드로 이루어진 묶음이다. Data filed는 node는 integer, character 등 노드가 보유할 실제 데이터..
-
[ 복잡도 ] 정렬 알고리즘의 복잡도Computer Science/자료 구조 2022. 12. 26. 21:43
정렬 알고리즘에 따른 복잡도 Algorithms space complexity time complexity 최악 최선 평균 최악 bubble O(1) O(n) O(n^2) O(n^2) heap O(1) O(n log n) O(n log n) O(log n) insertion O(1) O(n n) O(n^2) O(n^2) merge O(n) O(n log n) O(n log n) O(log n) quick O(log n) O(n log n) O(n log n) O(n^2) selection O(1) O(n^2) O(n^2) O(n^2) shell O(1) O(n) O(n^1.25) O(n^1.25) smooth O(1) O(n) O(n log n) O(n log n) 자료 구조 별 시간 복잡도 Big-O ..