알기쉽게 해설한 데이터구조 고 갑 승 한남대학교 알기 쉽게 해설한 데이터 구조 고 갑 승 한남대학교

알기쉽게 해설한 데이터구조 제 1장 자료구조의 기본 1.1 알고리즘 1.2 알고리즘 분석 1.3 점근 표기법

1.1 알고리즘 알고리즘의 정의 알고리즘의 표현방법 알고리즘의 기준

알고리즘의 정의 “ 어떤 특정 문제를 해결하기 위한 절차와 방법을 명확하게 기술해 놓은 명령들의 집합 ” 알기쉽게 해설한 데이터구조 알고리즘의 정의 “ 어떤 특정 문제를 해결하기 위한 절차와 방법을 명확하게 기술해 놓은 명령들의 집합 ” (예) 서울에서 부산까지 가는 문제 해결

알고리즘의 표현 자연어(영어, 한글 등) 흐름도(flowchart) PASCAL, C, C++, JAVA 의사코드(pseudo code)

알고리즘의 기준 입력(input) : 외부에서 제공하는 0개 이상의 데이터가 존재 출력(output) : 적어도 하나 이상의 결과가 출력 명확성(definiteness) : 기술된 명령들이 명확 유한성(finiteness) : 유한 번 수행 후 반드시 종료 실제성(effectiveness):모든 단계의 명령들이 실행 가능

1.2 알고리즘의 분석 정확성(correctness) 수행량(시간복잡도) 사용공간(공간복잡도) 단순성(simplicity) 알기쉽게 해설한 데이터구조 1.2 알고리즘의 분석 정확성(correctness) 수행량(시간복잡도) 사용공간(공간복잡도) 단순성(simplicity) 최적성(cptimality)

1. 정확성(correctness) 정확성이란? “ 알고리즘이 타당한 입력이 주어졌을 때 유한 시간 내에 계산이 수행되어 올바른 결과를 출력하는 것 ” 정확성 증명하기 위한 가장 간단한 방법 [ Hand simulration ] 정확성 증명하기 위한 가장 유용한 방법 [ 수학적 귀납법 ]

[수학적 귀납법] 명제 P(n)이 모든 자연수 n에 대하여 성립하는 것을 증명? n=1 일 때, 명제 P(n)이 성립한다. n=k 일 때, 명제 P(n)이 성립한다고 가정하면 n=k+1 일 때에도 명제 P(n)이 성립한다.

2. 수행량(time complexity) “ 알고리즘에 의하여 수행되는 작업의 양, 즉 시간은 어떻게 측정될 수 있는가? ” 기본연산 : 가장 중요한 연산들로만 그 수행량을 측정한다면 효과적으로 수행량을 비교할 수 있는 있는데 이때 선택된 연산을 기본 연산이라 한다.

(예1) 두 행렬 n*n의 곱을 계산하는 알고리즘 int matrixmultiply(int *a, int *b, int *c) { /* 행렬 c = 행렬 a * 행렬 b */ int i, j, k; for(i=0; i<n; i++) for(j=0; j<n; j++){ c[i][j] = 0; for(k=0; k<n; k++) c[i][j] = c[i][j] + a[i][k]*b[k][j]; } return(0);

3. 사용공간(space complexity) “알고리즘이 수행되기 위해 필요로 하는 메모리 공간” 공간 복잡도의 정의 고정적으로 요구되는 공간을 제외하고, 가변적으로 요구되는 공간들을 계산 최악의 경우(worst-case) 평균의 경우(average-case)

4. 단순성(Simplicity) “ 알고리즘의 정확성증명과 알고리즘에 대한 프로그램의 작성과 디버깅, 그리고 수정을 더 쉽게 한다.”

5. 최적성(optimality) 최적의 알고리즘 “ 최소의 수행량으로 더 적은 수행량을 갖는 알고리즘은 없다.”

(예2) n개의 원소로 구성된 리스트에서 가장 큰 원소를 찾는 알고리즘 int FindMax(int *list, n) { int i , max = list[0]; for(i=0; i<n; i++) if(max < list[i]) max = list[i]; return max; }

1.3 점근 표기법 점근 표기법을 사용하는 이유 알고리즘의 수행량 비교를 위하여 알고리즘의 차수로 표현 표현법 첫째, 같은 문제를 해결하기 위하여 작성된 두 알고리즘의 시간 복잡도를 비교 둘째, 입력되는 자료의 크기 변화에 따른 수행 증가를 예측할 수 있음 표현법 O(big oh) 표현법 Ω(big omega) (big theta)

가정: f, g를 자연수 집합 N에서의 함수라 하자. (1) O(big oh)표현법 f(n) ≤ c * g(n) * n ≥ n0 인 n에 대하여, 함수f(n)의 차수가 g(n)보다 작거나 같다 * n이 커짐에 따라 f(n)의 값보다 g(n)의 값이 더 빠르게 증가한다면, 위의 식은 항상 참일 것이다. * “f(n)의 증가 비율(rate)은 g(n)의 비율을 넘지 않는다.”는 의미 * 입력의 크기가 n일 때 어떤 알고리즘의 수행 시간이 f(n)이라면, 알고리즘의 수행 시간은 g(n)보다 빠르게 증가하지는 않는다는 의미 * big-oh 표기법으로 표현 : f(n) = O(g(n)) [예] * n≥2를 만족하는 모든 n에 대하여, 2n+2≤3n이므로, 2n+2=O(n) * n≥2를 만족하는 모든 n에 대하여, 2n+3≤2n2이므로, 2n+3=O(n2) * g(n)은 모든 n(n≥2)에 대하여 f(n)의 상한(unper bound) * f(n)=O(g(n))에 있어 O(n)이 O(n2)보다는 더 의미있는 표기법.

(2) Ω(big omega) f(n) ≥ c * g(n) * n ≥ n0인 n에 대하여, 함수 f(n)의 차수가 g(n)보다 크거나 같다 * n이 커짐에 따라 f(n)의 값이 g(n)의 값보다 더 빠르게 증가한다면, 위의 식은 항상 참일 것이다. * “f(n)의 증가 비율은 최소한 g(n)의 비율정도는 된다”는 의미 * big-omega 표기법으로 표현 : f(n) = Ω(g(n)) [예] * n≥1를 만족하는 모든 n에 대하여, 3n+3 ≥ 3n이므로, 3n+3=Ω(n) * Ω(n)은 g(n)보다 차수가 크거나 같은 함수들의 집합으로 이야기할 수 있으며, 이때 g(n)은 하한(lower bound)이 되는 것이다.

(3)ℴ (big theta) c1 * g(n) ≤ f(n) ≤ c2 * g(n) * n ≥ n0인 모든 n에 대하여, 임의 함수 f(n)의 차수가 같은 함수 * n이 커짐에 따라 f(n)의 값이 g(n)의 값과 상수 배 정도의 차이로 증가한다면, 위의 식은 참 * “f(n)는 g(n)과 같은 비율로 증가한다.” * big-theta 표기법으로 표현 : f(n) = ℴ(g(n)) [예] n≥2를 만족하는 모든 n에 대하여, 3n ≤ 3n + 2 ≤ 4n이므로, 3n + 2 = ℴ(n)이다

점근 표기법의 표현 Big-oh의 표현 : 알고리즘의 수행시간이 이보다 걸리지 않는다는 것을 개략적으로 나타낼 때 이용 Big-omega의 표현 : 문제를 풀기 위해서는 어느 정도의 시간은 필요하다는 문제의 하한을 나타낼 때 Big-theta : 최적 알고리즘을 나타낼 때

n 값의 변화에 따른 알고리즘의 시간 복잡도를 나타내는 여러 함수의 함수 값 변화 log n n n log n n2 n3 2n 0 1 0 1 1 2 1 2 2 4 8 4 2 4 8 16 64 16 3 8 24 64 512 256 4 16 64 256 4096 65536 5 32 160 1024 32768 4294967296