자료구조란?
- 데이터의 탐색, 읽기, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체
- 자료구조를 설계할 때에는 데이터와 데이터에 관련된 연산을 함께 고려
추상데이터타입
- 데이터에 대한 추상적인 연산(탐색, 읽기, 쓰기, 삭제)들로 구성된 것
- 이때 '추상적'이란, 연산을 구체적으로 어떻게 구현할지 세부 명세를 포함하지 않은 것
추상데이터타입과 자료구조의 관계
- 자료구조는 추상데이터타입을 실제 프로그램으로 구현한 것
- 자료구조에는 대표적으로 연결리스트, 스택, 큐, 트리, 해시테이블, 그래프 등이 존재
시간복잡도
- 자료구조의 효율성은 자료구조에 대해 수행되는 연산의 수행시간으로 측정되며 연산의 수행시간 측정 방식은 시간 복잡도와 공간 복잡도에 기반한다.
- 대부분의 알고리즘이 비슷한 크기의 메모리 공간을 사용하기 때문에 알고리즘의 성능은 공간보다는 시간의 영향을 많이 받는다.
- 알고리즘이 실행되는 동안에 사용되는 기본적인 연산 횟수를 함수로 나타내는 것이 시간복잡도이다.
*이때 기본연산이란 앞서말한 탐색, 읽기, 쓰기, 삭제가 아닌 데이터 간 크기 비교, 데이터 읽기 및 갱신 등과 같은 단순한 연산을 의미한다.
수행시간의 분석 3종류
수행시간을 입력의 크기에 대한 함수로 표현하기 위해 점근 표기법을 사용한다.
<점근 표기법>
- 최악의 경우를 기준으로 하는 최악경우 분석
- 가장 빠른 수행시간을 분석하는 최선경우 분석
- 균등분포를 가정해 분석하는 평균경우 분석
1. O (Big O) 표기법 (최악경우 분석)
[O 표기법 정의]
N0 과 같거나 큰 모든 N에 대해 f(N)이 cg(N) 보다 크지 않음이 성립되는,
즉, f(N)을 cg(N)보다 작거나 같게 하는 양의 상수 c와 N0이 존재하면 f(N)=O(g(N)) 이다.
f(N)=O(g(N))은 N0보다 큰 모든 N에 대해서 f(N)이 g(N)에 미치지 못한다는 뜻으로, 특정한 값 N0 이상에서는 이 사실이 항상 성립되어야 한다.
이때 g(N) 을 f(N)의 상한이라고 한다. 상한은 g(N) 이상으로 더 이상 나쁠 수 없다는 것을 의미하므로 f(N)은 최악 중 최선의 상황이라고 볼 수 있다.
y축을 수행시간이라고 할 때 f(N) 선을 기준으로 위에 있으면 수행시간이 긴 나쁜 알고리즘, 아래 쪽에 있으면 수행시간이 짧은 좋은 알고리즘이다. 이때 그 기준선을 최악의 경우라고 말한다.
f(N) 선과 cg(N) 선 사이의 파란 간격이 좁아야 신뢰가 높다고 평가된다.
O-표기 찾는 방법
- 주어진 수행시간의 다항식에서 최고 차수 항 취한 뒤
- 그 항의 계수 제거하여 g(n) 정함
예를 들어, 2n*2 + 3n + 5 에서는 O(n*2) 이다.
Algorithm sum1 (A, n) :
sum = 0
for i = 0 to n-1 do # n번 반복하는 반복연산이 O(n)을 의미한다
if A[i]%2 == 0 :
sum+=A[i]
return sum
2. Ω 표기법 (최선경우 분석)
[ Ω 표기법 정의]
N0 과 같거나 큰 모든 N에 대해 f(N)이 cg(N) 보다 크거나 같음이 성립되는,
즉, f(N)을 cg(N)보다 크거나 같게 하는 양의 상수 c와 N0이 존재하면 f(N)=Ω(g(N)) 이다.
f(N)=Ω(g(N))은 N0보다 큰 모든 N에 대해서 f(N)이 g(N)보다 작지 않다는 뜻으로, 특정한 값 N0 이상에서는 이 사실이 항상 성립되어야 한다.
이때 g(N) 을 f(N)의 하한이라고 한다. 하한은 g(N) 이상으로 더 이상 좋을 수 없다는 것을 의미하므로 f(N)은 최선 중 최악의 상황이라고 볼 수 있다.
y축을 수행시간이라고 할 때 f(N) 선을 기준으로 위에 있으면 수행시간이 긴 나쁜 알고리즘, 아래 쪽에 있으면 수행시간이 짧은 좋은 알고리즘이다. 이때 그 기준선을 최선의 경우라고 말한다.
마찬가지로 f(N) 선과 cg(N) 선 사이의 초록 간격이 좁아야 신뢰가 높다고 평가된다.
Ω -표기 찾는 방법
- 주어진 수행시간의 다항식에서 최고 차수 항 취한 뒤
- 그 항의 계수 제거하여 g(n) 정함
예를 들어, 2n*2 + 3n + 5 에서는 O(n*2) 이다.
O-표기와 찾는 방법이 동일하다.
3. Θ 표기법 (평균경우 분석)
[ Θ 표기법 정의]
N0 과 같거나 큰 모든 N에 대해 f(N)이 c2g(N) 보다 크거나 같고 c1g(N) 보다 작거나 같음이 성립되는,
양의 상수 c1, c2, N0이 존재하면 f(N)= Θ(g(N)) 이다.
일반적으로 빅오 표기와 오메가 표기가 동일한 경우에 사용한다.
즉, O(g(N)) = Ω(g(N)) 인 경우를 Θ(g(N)) 라고 한다.
N이 증가함에 따라 f(n)이 N0보다 큰 모든 N에 대해서 c1g(N)보다 크지 않고 c2g(N)보다 작지 않다.
자주 사용되는 함수의 O-표기
알고리즘 수행시간은 3가지 표기 중 주로 O-표기를 사용한다.
다음은 수행 시간을 위해 자주 사용되는 함수의 O-표기이다.
순서대로 상수시간이 가장 빠른 시간, 지수시간이 가장 느리고 성능이 좋지 않은 시간이다.
*지수시간보다 성능이 좋지 않은 O(n!)도 존재한다.
예를 들어, 입력값 n=10*6 일때, 선형시간의 알고리즘으로 계산하면 10*6번 계산해야 한다. 반면 로그시간 알고리즘을 사용하면 6번만 계산하면 된다. 이런 식으로 알고리즘의 성능에 따라 연산의 수행시간이 천차만별로 구분되게 된다.
<시간복잡도의 적용>
O(1) 은 해시라고 불리며, 단 한 번의 연산만으로 정보를 찾을 수 있다.
O(logN)은 이진 트리 구조에서 이진 탐색 하는 함수이다.
O(N) 이 가장 일반적으로 많이 적용되는 함수로 최대값을 찾는다.
O(NlogN) 은 병합정렬, 퀵정렬에 적용된다.
O(N*2) 는 선택정렬, 삽입정렬에 적용된다.
O(2*N) 은 모든 부분집합을 검사할 때 적용된다.
위 그래프는 각 알고리즘 별 함수의 증가율을 비교한다.
y축을 수행시간이라고 할 때, logN에 비해 N! 일 때 수행시간이 급격하게 높아지는 것을 확인할 수 있다. 최고차항의 차수가 높으면 높을 수록 성능이 나쁘다고 볼 수 있다.
가장 이상적인 알고리즘은 빅 오와 빅 오메가가 동시에 낮은 알고리즘, 즉 빅 세타가 낮은 알고리즘을 선택하는 것이다.
하지만 대부분 빅 오와 빅 오메가가 반비례한다. 이에 최악의 상황이 발생하는 경우를 가정하고,
Big O가 낮은 알고리즘을 선택하는 것이 좋다.