자료 구조 (1) : 자료 구조와 시간 복잡도(Big(O))

자료 구조

데이터(자료)를 효율적으로 사용할 수 있도록 데이터를 구성하는 방법

 

자료 구조의 예시(Java)

추상 자료 구조(인터페이스)	구현체
List	ArrayList, LinkedList
Set	HashSet, LinkedHashSet, TreeSet
Map	HashMap, LinkedHashMap, TreeMap
Queue	LinkedList, ArrayDeque, PriorityQueue

 

그렇다면 얼마나 효율적인지는 어떻게 알 수 있을까요?

 

시간 복잡도, 공간 복잡도

 

알고리즘의 효율성을 분석할 때는 다음 두 가지 질문을 생각합니다

 

1. 시간 복잡도 : 이 알고리즘은 끝나는 데 얼마나 시간이 걸릴까?

2. 공간 복잡도 : 이 알고리즘을 실행하기 위해 얼마나 많은 공간이 필요할까?

 

시간 복잡도를 바탕으로 효율성을 계산하는 방법을 알아 봅시다

시간 복잡도를 계산하는 표기법에는 대표적으로 세 가지가 있습니다

 

Big-Omega (Ω) : 알고리즘이 수행되는 최소 연산량

Big-Theta (Θ) : 알고리즘이 수행되는 평균 연산량

Big-O : 알고리즘이 수행되는 최악 연산량

 

ex) 무작위로 1, 2, 3, 4, 5가 적힌 5칸의 배열에서 3을 찾는 경우
Big-Omega : 첫 칸에 3이 존재 => 1
Big-Theta : 평균적으로 배열의 중간에 있음 => 3

Big-O : 마지막 칸에 3이 존재 => 5

이 중에서 시간 복잡도를 계산할 때는 일반적으로 모든 경우를 만족하는 Big-O 표기법이 사용됩니다

또한, 이해를 돕기 위해 위의 예시에서는 상수값을 적었지만 실제 시간 복잡도 계산은 입력값(n)의 크기가 커짐에 따라 수행시간이 얼마나 커지는 가를 계산합니다

Big-O 표기법은 다음과 같은 특징들이 있는데 n이 무한대로 커진다고 생각하는 것이 이해를 도울 것입니다

• 상수항은 무시 : 입력값의 크기가 변해도 상수항은 변하지 않으므로
• 최고차항만 표시 : 입력값의 크기가 변할 때 낮은 차수항은 최고 차수항에 비해 끼치는 영향이 미미하기 때문
• 최고차항의 계수는 무시 : 계수가 끼치는 영향은 미미하기 때문
• O(n + c) = O(n)
• O(cn) = O(n), c > 0

ex) 2n² + n + 5 의 시간 복잡도는 O(n²)

ex) 무작위로 1, 2, 3, 4, 5가 적힌 5칸의 배열에서 3을 찾는 경우

Ω(1), Θ((n+1)/2) = Θ(n), O(n)

 

시간 복잡도 크기 순서

a > 1 일 때

O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n²) < O(aⁿ) < O(n!)

 

 

대표적인 시간 복잡도 예시

• O(log(n)) : 데이터의 요소를 절반 씩 줄여가며 탐색(이진 탐색)
• O(n) : 리스트의 모든 요소를 하나씩 확인(선형 탐색)
• O(nlog(n)) : 배열을 분할(O(logn))하고 병합(O(n))하는 병합 정렬
• O(nm) : n * m 행렬의 모든 셀을 탐색
• O(n2) : 중첩된 반복문으로 두 요소를 비교하는 버블 정렬
• O(n3) : 삼중 반복문을 사용하는 행렬의 곱셈
• O(2n) : n개의 원소로 구성된 집합의 모든 부분 집합 갯수
• O(n!) : 모든 순열