아래 내용은 부산대학교 소프트웨어 교육센터 ‘인공지능전문가 교육과정 - 데이터사이언스: 데이터 구조’ 수업 내용을 복습하며 제 언어로 다시 정리한 글 입니다.
자료구조와 알고리즘
자료구조
정의: 데이터를 담고 조직화 시키는 틀
목적: 편리하고 효율적인 데이터 이용
주요 종류: 선형자료구조, 비선형자료구조
선형자료구조
정의: 데이터 마다 순서(인덱스) 부여되는 자료구조.
특징: 각 자료 간 앞 뒤로 1:1 대응, 선형 구조를 이룬다.
종류: 리스트, 큐, 스택 등
비선형자료구조
정의: 데이터에 순서(인덱스) 부여되지 않는다. 대신 데이터 간 1:n, n:n 대응된다.
종류: 트리, 그래프 등
알고리즘
정의: 문제 해결 절차
어떤 절차가 알고리즘이 되기 위한 조건:
- 입력은 없어도 된다. 하지만 반드시 1개 이상 출력을 가져야 한다.
- 명백성: 각 명령어의 의미가 명확해야 된다.
- 유한성: 무한루프 돌면 안된다. 반드시 언젠가 끝나야 한다.
- 유효성: 각 명령어는 실행가능해야 한다.
추상자료형
정의: 속성, 연산이 명시되었지만 그 구현 방식이 구체적으로 정해지지 않은 ‘클래스’ 와 같다.
- 연산 구현 방식이 구체적으로 설정되는 경우(예: 배열 자료구조 사용해서 연결리스트 연산 구현), 추상자료형에서 자료구조(자료형)가 된다.
알고리즘 성능 분석 방법
1. time 등 모듈 써서 직접 실행시간 측정하는 방법
알고리즘 별 객관적 성능 비교가 어렵다.
2. 알고리즘 복잡도 분석하는 방법
1번에 비해 객관적 성능 비교 가능하다.
산술, 대입, 비교, 이동. 4개 기본 연산 횟수로 알고리즘 복잡도 나타낸다.
$\Rightarrow$ 4개 기본 연산 횟수로 알고리즘의 ‘시간 복잡도 함수’를 나타낸다.
예)
$n^{2}$ 를 구하는 문제
1 번 방법 : $n$ * $n$ 을 해서 구하는 방법
- n에 숫자 대입연산(1) + 두 n 을 곱하는 곱셈연산(1)
- 총 2번의 기본연산 수행. 시간 복잡도 함수 $T(n) = 2$ 가 된다.
2 번 방법 : for문을 써서 n을 n번 더하는 방식
- n을 n번 더하는 덧셈연산(n) + n에 숫자를 n+1 번 대입하는 대입연산(n+1)
- 총 2n+1 번 기본연산 수행. 시간 복잡도 함수 $T(n) = 2n+1$ 가 된다.
첫 번째 방법은 n에 상관없이 항상 일정한 시간복잡도 값이 나온다. 반면 두 번째 방법은 n 크기 변화에 따라 시간복잡도가 선형으로 증가한다. 첫 번째 방법이 더 좋은 알고리즘이다.
3. 시간 복잡도 분석 방법
- 최악경우 분석: 시간 상한선 정해 놓고. 여러 알고리즘 중 최악의 경우에도 시간 상한선 보다 적은 시간 걸리는 알고리즘 채택
- 평균경우 분석: 입력값의 모분포를 균등분포로 둔다. 여러 입력에서의 알고리즘 수행 시간 표본분포를 구하고, 그 모분포 기댓값을 추정한다. 여러 알고리즘 중 기댓값이 가장 작은 알고리즘을 선택한다.
- 최선경우 분석: 가장 빠른 수행시간이 더 작은 알고리즘 찾기
알고리즘 성능측정을 위해 최악경우 분석을 사용한다.
시간복잡도 빅오 표기법
정의: 시간복잡도 함수 최고차항 만으로 알고리즘 시간 복잡도 나타내는 방법.
최고차항으로 나타낸 시간 복잡도는 시간상한 나타낸다. 즉 최악 경우 걸리는 시간 나타낸다.
예) 시간복잡도 함수가 $T(n) = n^{2} + n + 1$ 이면, 알고리즘 시간 복잡도는 $O(n^{2})$
- 최악 경우 $n^{2}$ 만큼 시간 소요된다는 말이다.
조건: 어떤 임의 양의 상수 $c$, $n_{0}$ 에 대해. $n > n_{0}$ 일 때 $0 \leq f(n) \leq cg(n)$ 성립하기만 하면. $f(n) = O(g(n))$ 이다.
- $f(n)$: 시간복잡도 함수
- $g(n)$: 시간복잡도 함수의 최고차항(계수도 고려하지 않는다)
예)
어떤 알고리즘의 시간복잡도 함수가 $f(n) = 5$ 이면, 그 알고리즘의 시간복잡도를 빅오 표기법으로 나타내면 $O(1)$ 가 된다.
- $c = 10, n_{0} = 1$ 일 때. $n \ge 1$ 에 대해 $0 \leq 5 \leq 10$ 만족한다.
예)
어떤 알고리즘의 시간복잡도 함수가 $f(n) = 2n+1$ 이면, 그 알고리즘의 시간복잡도를 빅오 표기법으로 나타내면 $O(n)$ 이 된다.
- $c=3, n_{0} = 2$ 일 때. $n \ge 2$ 에 대해 $2n+1 \leq 3n$ 만족한다.
빅오 표기법 종류
시간복잡도 함수 유형 별 시간 복잡도 빅오 표기
$T(n) = 100$ $\Rightarrow$ $O(1)$
상수시간. 입력값 크기와 상관없이 일정. 사칙연산, if문 등
$T(n) = 2log{N}$ $\Rightarrow$ $O(log{N})$
로그시간. 이진트리 등
$T(n) = 4N+8$ $\Rightarrow$ $O(N)$
선형시간. for 문 등
$T(n) = Nlog{N}+N$ $\Rightarrow$ $O(Nlog{N})$
로그 선형시간. 퀵, 병합, 힙 정렬 등
$T(n) = 3N^{2}+5N+4$ $\Rightarrow$ $O(N^{2})$
제곱시간. 2중 for 문 등
$T(n) = 2N^{3} +3N^{2} +1$ $\Rightarrow$ $O(N^{3})$
세제곱시간.
$T(n) = 2^{N}$ $\Rightarrow$ $O(2^{N})$
지수시간. 피보나치수열 등.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 빅오 표기법에 따른 알고리즘 시간복잡도(시간상한) 비교
plt.figure(figsize=(10,8))
xx = np.linspace(0, 100, 10000)
const = [1 for i in xx]
def log(xx) :
return np.log2(xx)
def linear(xx) :
return xx
def linear_log(xx) :
return xx*np.log2(xx)
def squared(xx) :
return xx**2
def cubic(xx) :
return xx**3
def expo(xx) :
return 2**xx
plt.ylim(0, 200)
plt.plot(xx, const, label='상수시간')
plt.plot(xx, log(xx), label='로그시간')
plt.plot(xx, linear(xx), label='선형시간')
plt.plot(xx, linear_log(xx), label='로그선형시간')
plt.plot(xx, squared(xx), label='제곱시간')
plt.plot(xx, cubic(xx), label='세제곱시간')
plt.plot(xx, expo(xx), label='지수시간')
plt.legend()
plt.xlim(0, 100)
plt.title('빅오 표기법에 따른 알고리즘 시간복잡도 (시간상한) 비교')
plt.show()
