1) 선형 데이터 구조
항목들이 순차적 차례에 따라 접근되지만 순차적으로 저장되어야 하는 것은 아니다.
ex) 연결 리스트, 스택, 큐
2) 비선형 데이터 구조
항목들이 비선형의 차례로 저장/접근된다.
ex) 트리, 그래프
- 추상 데이터형(Abstract Data Type)
보통의 사용자 정의 데이터형은 연산과 함께 정의된다. 문제를 푸는 과정을 단순화시키기 위해 데이터 구조와 연산을 합쳐 놓은 것을 추상 데이터형이라고 하는데, ADT는 두 부분으로 구성된다.
1. 데이터의 선언
2. 연산의 선언
주로 사용되는 ADT에는 연결 리스트,스택,큐,우선순위 큐,이진 트리, 딕셔너리,서로 소 집합, 해시 테이블, 그래프 등 다수가 있다.
ex) 스택은 데이터를 데이터 구조에 저장할 때 LIFO방식을 사용한다. 스택에 가장 나중에 집어넣은 항목이 제일 먼저 꺼내지는 항목이 되는 것이다. 스택에서 주로 사용되는 연산에는 스택 만들기, 스택에 항목 집어넣기, 스택에서 항목 꺼내기, 스택의 맨 위에 있는 항목 찾기, 스택 안의 항목 개수 찾기 등이 있다.
ADT를 정의할 때는 구체적인 구현은 신경 쓰지 않아도 된다. 실제 사용할 때 구현이 중요하다. 사용 용도에 따라 그에 알맞는 ADT들이 쓰이며 몇몇 ADT는 특정 용도에 최적화되어 있다.
- 알고리즘: 주어진 문제를 풀기 위한 단계별 지시사항들이다.
- 왜 알고리즘을 분석하는가?
한 가지 문제를 푸는 데 여러 가지 알고리즘이 있을 수 있다. 알고리즘 분석은 시간과 공간적으로 어느 것이 가장 효율적인지 알 수 있게 해준다.
- 알고리즘 정렬의 목적
알고리즘 정렬의 목적은 알고리즘을 비교하는 것인데, 주로 수행 시간으로 비교하지만 다른 요인들로 비교할 때도 있다.
- 수행 시간 분석이란 무엇인가?
문제의 크기가 증가함에 따라 처리 시간이 얼마나 증가하는지를 분석하는 것이다. 입력 크기는 입력되는 항목의 개수인데 문제의 종류에 따라 입력의 종류도 달라진다. 일반적으로 다음과 같은 종류의 입력들을 볼 수 있다.
-배열의 크기
-다항식의 차수
-행렬의 항목 개수
-이진으로 표현된 입력의 비트 수
-그래프에서의 정점과 간선
- 어떻게 알고리즘을 비교하는가?
// 자람 차수 부분 참조
여기서는 '증가율'이라 표현한다.
 |
| 자주 사용되는 증가율 목록 // 모르는 거는 그냥 넘어가기 |
- 분석의 종류
최악의 경우
알고리즘이 오래 걸리는 경우이다.
알고리즘이 느리게 수행되도록 하는 것을 입력으로 한다.
최선의 경우
알고리즘이 제일 적은 시간이 걸리게 하는 경우이다.
알고리즘이 가장 빨리 수행되도록 하는 것을 입력으로 한다.
평균의 경우
알고리즘의 예상 수행 시간을 제시한다.
입력이 무작위라고 가정한다.
(하한 시간=< 평균 시간 =< 상한 시간)
ex)
f(n) = n^2 + 500, 최악의 경우
f(n) = n + 100*n + 500, 최선의 경우
* 평균의 경우에는 입력을 정의한 후 수식을 만든다.
- 점근적 표기법
최선, 평균, 최악의 경우에 대한 수식이 있을 때, 이 세개의 경우 모두에 대한 상한과 하한을 찾아야 한다. 이러한 상한과 하한을 표현하기 위해 필요한 문법을 알아야한다.
1) 빅-오 표기법
이 표기법은 주어진 함수에서 엄밀한 상한을 찾게 해준다. 일반적으로 f(n) = O(g(n))으로 표현된다. 이 것은 n의 값이 클 때, f(n)의 상한이 g(n)이라는 말이다.
ex)
f(n) = n^4 + 100*(n^2) + 10*n + 50 일 때 n^4이 g(n)이다.
빅-오 표기법의 정의
O(g(n)) = {f(n): n > n0 인 모든 n에 대해 0 =< f(n) =< c*(g(n))을 만족하는 양의 상수 c와 n0 이 존재한다.}
빅-오 시각화
O(g(n))은 g(n)의 증가율보다 작거나 같은 함수들의 집합이다.
빅-오 예제
예제1) f(n) = 3*n + 8 의 상한을 구하라.
n >= 8인 모든 n에 대하여 3*n + 8 =< 4*n이다.
따라서 3*n + 8 = O(n)이며 c = 4, n0 = 8이다.
예제2) f(n) = n^2 + 1의 상한을 구하라.
예제3) f(n) = n^4 + 100*n^2 + 50의 상한을 구하라.
예제4) f(n) = 2*n^4 - 2*n^2의 상한을 구하라.
예제5) f(n) = n의 상한을 구하라.2) 오메가 표기법
이 표기법은 주어진 알고리즘에 대해 엄밀한 하한을 찾게 해주며 f(n) = Ω(g(n))으로 표현된다. 이는 n의 값이 클 때, f(n)의 엄밀한 하한이 g(n)이라는 말이다.
오메가 표기법 정의
Ω(g(n)) = {f(n): n >= n0 인 모든 n에 대해 0 =< c*g(n) =< f(n)을 만족하는 양의 상수 c와 n0이 존재한다}
오메가 예제
예제1) f(n) = 5*n^2의 하한을 구하라.
0 =< c*n =< 5*n^2 => c*n =< 5*n^2 => c=1, n0=1
예제2) f(n) = 100*n + 5 =/= Ω(n^2)을 증명하라
0 =< c*n^2 =< 100*n + 5
n >= 1인 임의의 n에 대해 100*n + 5 =< 100*n + 5*n = 105*n
c*n^2 =< 105*n => n*(c*n - 105) =< 0
n이 양수이므로 => c*n -105 =< 0 => n =< 105/c
=> n이 어떤 상수보다 작을 수 없으므로 모순이 된다.
예제3) n! = Ω(2^n), n^3 = Ω(n^2), n = Ω(logn)
- 세타 표기법
이 표기법은 주어진 함수(알고리즘)의 상한과 하한이 같은지 아닌지를 결정한다. 알고리즘의 평균 수행 시간은 항상 하한과 상한 사이에 존재한다. 만역 상한(O)과 하한(Ω)이 같다면 세타(Θ)표기법 역시 같은 증가율을 갖게 된다.
세타 표기법의 정의
Θ(g(n)) = {f(n): n >= n0인 모든 n에 대해 0 =< c1*g(n) =<f(n) =< c2*g(n)을 만족하는 양의 상수 c1, c2와 n0이 존재한다}
세타 예제
예제1) f(n) = (n^2)/2 - n/2의 Θ한계를 구하라.
n >= 1인 모든 n에 대하여 n^2 =< (n^2)/2 - n/2 =< n^2이다.
따라서 (n^2)/2 - n/2 = Θ(n^2)이며 c1 = 1/5, c2 = 1이고 n0 = 1이다.
예제2) n =/= Θ(n^2)임을 증명하라.
c1*n^2 =< n =< c2*n^2 => n =< 1/c1일 때만 참이다.
따라서 n =/= Θ(n^2)이다.
c1*n^2 =< 6*n^3 =< c2*n^2 => n =< c2/6일 때만 참이다.
따라서 6*n^3 =/= Θ(n^2)이다.
예제4) n =/= Θ(logn)임을 증명하라.c1*logn =< n =< c2*logn => n >= n0인 임의의 n에 대하여 c >= n/logn 는 불가능하다.
댓글 없음:
댓글 쓰기