⭐자료 구조(data structure)
효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합
복잡도 종류
1. 시간 복잡도
2. 공간 복잡도
1. 시간 복잡도 (Time Complexity)
‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계’
어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다.
빅오 표기법
인도의 왕이 지혜로운 사람에게 상을 내리고 싶어 했는데, 이 사람은 체스판을 가득 채울 만큼의 밀알을 원했다.
조건은 체스판의 1알의 밀알을, 두번째 칸에는 2알의 밀알을, 세 번째 칸에는 4알의 밀알을... 이런 식으로 체스 판의 각 칸의 바로 이전 칸에 있는 밀알의 제곱한 양으로 채워지기를 바랐다. 왕은 흔쾌히 수락했다.
하지만 체스판을 다 채우면, 총 64칸으로 마지막 칸에는 총 2⁶³ 알의 밀알이 필요하다. 전체 체스판에서 얻을 수 있는 밀알은 1.8446744*10¹⁹개이고, 한알이 0.01 그램이라고 가정해도 1천8백4십억 톤이다. 왕이 거덜 나지 않을까..?
이러한 이유로 증가율을 계산할 때 최고차항만을 고려한다.
‘가장 영향을 많이 끼치는’ 항의 상수 인자를 빼고 나머지 항을 없앤 것이다.
다른 항들이 신경 쓰일 수도 있지만 증가 속도를 고려한다면 그렇지 않다.
입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고, 다른 것은 그에 비해 미미하기 때문에 이것만 신경 쓰면 된다는 이론이다.
시간 복잡도의 존재 이유
효율적인 코드로 개선하는 데 쓰이는 척도이다.
로직이 O(n²)의 시간 복잡도를 O(n)의 시간 복잡도 알고리즘으로 개선하면, 시간을 9초에서 3초로 개선할 수 있다.
시간 복잡도의 속도 비교
위의 표에서 볼 수 있듯이 O(n²), O(n)보다는 O(1)을 지향해야한다.
2. 공간 복잡도 (Space Complexity)
프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양
정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다.
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있다.
*고정 공간 : 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)
*가변 공간 : 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 즉 동적으로 필요한 공간
3. 자료 구조에서의 시간 복잡도
자료 구조의 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | O(logn) | O(logn) | O(logn) | O(logn) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
자료 구조 최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리(BST) | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
'CS 전공지식 > 자료 구조' 카테고리의 다른 글
| 3. 비선형 자료 구조 (0) | 2023.08.23 |
|---|---|
| 2. 선형 자료 구조 (0) | 2023.08.23 |
