최악 : 빅오 표기법
평균 : 빅세타 표기법
최선 : 빅오메가 표기법
빅오 표기법?
입력 값(n)에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도.
- O(1) : ex) stack의 push, pop
- O(log N) : ex) binary search 알고리즘, tree 형태 자료구조 탐색. 연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (log의 지수는 항상 2)
- O(N) : ex) 1중 for문 입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘
- O(N log N) : ex) 퀵 / 병합 / 힙 정렬. O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
- O(N^2) : ex) 2중 For 문, 삽입/거품/선택 정렬. O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
- O(2^N) : ex) fibonacci 수열. 빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘
선형 자료구조?
연속적으로 데이터가 나열되는 자료구조.
ex) 배열, 리스트, 스택, 큐 등
배열?
- 정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조.
- 각 데이터를 요소, 가르키는 번호를 인덱스라 한다.
- 인덱스는 0 ~ n-1
- 특정 인덱스의 데이터에 접근하는 시간 O(1)
- 검색 시간 O(n) - 데이터 검색 시 0 ~ n까지 탐색
- 삽입 시간 O(n) - 원하는 인덱스에 데이터 있을경우 뒷index데이터들을 한칸씩 미룬다
연결 리스트?
- 크기가 정해지지 않은 동적 자료구조.
- 여러 개의 노드가 다음 노드의 주소 값을 가지고 있다.
- 헤드 포인터와 테일 포인터로 시작과 끝을 알 수 있다.
- 인덱스가 없어서 특정 위치 데이터에 접근하는 데 배열보다 오래걸림.
- 검색 시간 O(n)
- 추가 시간 O(1) - 이전 노드가 가리키는 노드의 주소 값을 변경 하는 작업. but! 데이터를 추가하려는 위치로 이동하기까지 O(n)이 소요된다.
- 삭제 시간 O(n)
이중 연결 리스트?
- 앞 노드의 주소 값과 다음 노드의 주소 값을 모두 저장.
- 양방향 탐색이 가능하다.
- but 한 노드당 주소 값 2개를 저장해야 해서 메모리를 많이 차지한다.
- 연결 순서와 무관하게 노드 연속 탐색이 가능해 시간적으로 효율적이다.
- 구현이 기존 연결 리스트보다 어렵다.
원형 연결 리스트?
- 마지막 노드가 NULL값이 아니라 첫 번째 노드의 주소값을 가리키는 구조다.
- 삽입과 삭제 연산에 효율적이다.
스택?
- 데이터를 쌓는 형태, 마지막에 들어온 데이터가 먼저 나간다. LIFO
- 데이터 삽입 push, 데이터 삭제 pop - O(1)
- top - 마지막으로 저장한 인덱스
- 어떤 작업의 실행 취소 시 자주 자용됨. ex) 웹 뒤로가기
| 명령어 | 설명 | 복잡도 |
| push | 삽입 | O(1) |
| pop | 삭제 | O(1) |
| peek | 가장 위에 있는 데이터 확인 | O(1) |
| isEmpty | 비어있는지 확인 | O(1) |
| isFull | 가득 찼는지 확인 | O(1) |
큐?
- 데이터가 순차적으로 들어오는 형태. FIFO
- 맨 앞을 front, 맨 뒤를 rear
- 데이터 추가 시 맨 뒤에 추가됨 - 인큐.Enqueue
- 데이터 삭제 시 맨 앞에서 삭제 - 디큐.Dequeue
- ex) 작업 요청이 들어오는 순서대로 처리하는 프로세스가 CPU 할당 받기전 대기하는 준비queue
| 명령어 | 설명 | 복잡도 |
| enqueue | rear에 삽입 | O(1) |
| dequeue | front에 삭제 | O(1) |
| peek | front 데이터 확인 | O(1) |
| isEmpty | 비어있는지 확인 | O(1) |
| isFull | 가득 찼는지 확인 | O(1) |
덱? deque
양쪽 끝에서 데이터의 삽입, 삭제가 모두 가능한 자료구조.
스택+큐 형태이다.
'CS > 자료구조' 카테고리의 다른 글
| 자료구조 - 비선형 (1) | 2024.06.21 |
|---|