알고리즘 분석 알고리즘 정의 알고리즘 요건(Criteria) 특정한 일을 수행하기 위한 명령어의 유한 집합 입력 : (외부) 원인 >= 0 출력 : 결과 >= 1 명백성(definiteness) : 모호하지 않은 명확한 명령 유한성(finiteness) : 반드시 종료 유효성(effectiveness) : 기본적, 실행가능 Program = algorithm Flowchart is not algorithm

성능분석 성능분석을 배우는 목적 성능분석의 목적 성능평가의 기준 경험과 실전 훈련이 요구됨 프로그램에 대한 평가 능력 향상 보다 좋은 시스템 또는 알고리즘으로 개선 및 개발 시스템의 문제점 도출 성능평가의 기준 시스템이 원래의 명세와 부합하는가? 정확하게 동작하는가? 개발문서, 기술전수문서 및 사용법 설명서등 문서화가 잘 되어 있는가 ? 프로그램의 논리적 단위(즉, 함수)는 효과적으로 사용되고 있는가 ? 프로그램의 코드는 읽기 쉬운가? 기억장치를 효율적으로 사용하는가? 작업에 대한 프로그램의 실행시간은 받아들일 만 한가 ? 경험과 실전 훈련이 요구됨

성능평가 방법 성능분석(Performance Analysis) 성능측정(Performance Measurement) 특정 컴퓨터에 상관없이 알고리즘이나 프로그램의 시간과 공간을 추산하는 방법 복잡도 이론(Complexity Theory)에 기반을 둠 공간복잡도(Space Complexity) 시간복잡도(Time Complexity) 성능측정(Performance Measurement) 컴퓨터에 의존적인 실행시간 추산

공간 복잡도 공간 복잡도 : 프로그램이 필요로 하는 메모리 공간을 산출함 총 공간 요구량 : 고정 공간 요구량 + 가변 공간 요구량 프로그램이 필요로 하는 공간 고정 공간 요구 : 처리할 데이터의 량에 무관하게 항상 요구되는 공간 즉, 프로그램의 성능에 큰 영향을 주지 않음 명령어 공간(코드 저장 공간), 단순 변수, 고정크기의 구조화 변수, 성수, …. 가변 공간 요구 : 처리할 데이터의 량에 따라 다르게 요구되는 공간 프로그램의 성능에 큰 영향을 줌

가변 공간 요구량에 대한 예1 가변 공간 요구량을 고정 공간 요구량으로 변환 10M RAM A 대학 : 3,000명 성적처리 프로그램 자체 처리 읽기 40M RAM B 대학 : 16,000명 고정 공간 요구량 3 M RAM 1M 1M 1M 1M Slicing B 대학 : 16,000명

고정 공간 요구량 및 가변 공간 요구량의 예 프로그램 P가 문제 I를 푸는데 소요되는 가변 공간 요구량을 Sp(I)라 할때 Case - 1 Case - 2 : 반복기법 int sum(int a, int b) { return a+b; } int sum(int list[], int n) { int i, res= 0; for(i=0; i<n; i++) res = res + list[i]; }

Case - 3 : 순환기법 int sum(int list[], int n) { if(n < 0) return 0; else return list[n-1] + sum(list, n-1); } 즉, Sizeof(PSB)=6Byte라 할때 n=10 이면 Ssum(n) = 60 Bytes n=100 이면 Ssum(n) = 600 Bytes ...... n이 상당히 크면 Ssum(n) = 상당히 큰 가변 공간 요구됨 프로그램 A 프로그램 상태 정보 복원 프로그램 상태 정보 저장 프로그램 B 시스템이 불안정함.

시간 복잡도 프로그램 P에 소요되는 시간 : 컴파일 시간 + 실행시간 컴파일 시간 : 컴파일러의 속성에 따라 매우 다양하다 개발자의 입장에서는 중요한 요소임. 그러나, 알고리즘의 특성을 기술할 때에는 제외시킴 실행시간 프로그램이 완료될때 까지 소요되는 실제 시간을 측정하는 방법 프로그램의 성능측정에서 논의됨. 프로그램이 수행하는 연산의 횟수를 계산하는 방법 일반적인 알고리즘의 성능을 기술할 때 많이 사용됨 알고리듬에 대한 객관적인 성능 비교가 용이함. (즉, 컴퓨터나 컴파일러등에 독립적으로 알고리듬의 시간 복잡도를 계산하는 일반적인 방법)

연산횟수를 계산하는 방법 프로그램 단계의 정의 연산회수를 계산하는 방법 실행시간이 인스턴스 특성에 상관없이 구문적으로나 의미적으로 같은 뜻을 가지는 프로그램의 단위 연산회수를 계산하는 방법 방법론 Counter를 이용하는 방식 테이블 방식 점화식과 점근적 계산 방식

카운터를 이용하는 방식의 예 시작 int sum(int list[], int n) { int res=0; int counter=1; int i; for(i=0; i<n; i++) counter++; res = res + list[i]; } return res; int sum(int list[], int n) { int counter=1; for(i=0; i<n; i++) counter+=2; } res=0 i=0 counter=1 counter++ i<n res=res+list[i] return res; counter++ counter++ 끝

테이블 방식 예 절차 s/e 빈도수 총 단계수 int sum(int list[], int n) { int res=0; 각 문장에 대한 단계수 s/e(Steps/Execution) 결정 빈도수(Frequency : 문장이 실행되는 횟수) 계산 총 단계수(s/e * 빈도수)를 구한다. s/e 빈도수 총 단계수 int sum(int list[], int n) { int res=0; int i; for(i=0; i<n; i++) res = res + list[i]; } return res; 1 1 n+1 n 1 n+1 n

Matrix Addition

Recursive Function

Asymptotic Notation ( , ,  ) q Definition : [Big ] f(n)= (g(n)) (read as *f of n is big oh of g of n ) if there exist positive constants c and n0 such that f(n) ≤cg(n) for all n, n ≥ n0. e.g. , 3n+2= (n) as 3n + 2 ≤ 4n for all n≤2. 10n2 + 4n +2 =  (n2) as 10n2 + 4n + 2≤11n2 for all n≥5. (1), (log n), (n), (n log n), (n2), (n3), and (2n) - g(n) is an upper bound on the value of f(n) for all n, n≥n0 q Theorem 1.2 : If f(n) = amnm + … + a1n + a0, then f(n) = (nm)

q Definition : [ mega ] q Theorem 1.3 : f(n) = (g(n)) (read as f of n is omega of g of n) iff there exist positive constants c and n0 such that f(n) ≥cg(n) for all n, n ≥ n0. e.g., 3n + 2 = (n) as 3n + 2 ≥3n for all n ≥ 1. 10n2 + 4n + 2 = (n2) as 10n2 + 4n + 2 ≥ n2 for all n ≥ 1. - g(n) is a lower bound on f(n) q Theorem 1.3 : If f(n) = amnm + … + a1n + a0 and am > 0, then f(n) = (nm)

q Definition : [Theta] q Theorem 1.3 : f(n) =  (g(n)) (read as *f of n is theta of g of n ) iff there exist positive constants c1, c2 and n0 such that c1 g(n) ≤ f(n) ≤ c2g(n) for all n, n ≥ n0. e.g., 3n + 2 = (n) as 3n + 2 ≥ 3n for all n ≥ 2 and 3n + 2 < 4n for all n ≥ 2, so c1 = 3, c2 = 4, and n0 = 2. 10n2 + 4n + 2 = (n2). - g(n) is both an upper bound and lower bound on f(n) q Theorem 1.3 : If f(n) = amnm + … + a1n + a0 and am > 0, then f(n) = (nm)

Practical Complexities class of time complexities O(1): constant, 대부분 명령어가 한번에 실행되는 프로그램 O(log2n): logarithmic, 큰 문제를 분할해서 해결하는 프로그램 O(n): linear, 입력 아이템 N에 대해서 처리하는 프로그램 O(n·log2n): log-linear, 큰 문제를 분할해서 해결하고 합병하는 프로그램 O(n2): quadratic, 모든 쌍의 아이템을 처리하는 프로그램 O(n3): cubic O(2n): exponential O(n!): factorial polynomial time exponential time

알고리즘 분석 규칙 합의 규칙 : 프로그램 부분 p1 실행후 p2 실행 -> O(max(f(n), g(n))) 곱의 규칙 : T1(n)T2(n) -> O(f(n)g(n)) 배정문 : O(1) 순차문 : 합의 규칙 조건문 : 조건 평가 시간(O(1)) + 조건별 실행시간 최대치 반복문 : 루프반복회수 만큼 body 실행시간과 종료조건 평가시간(O(1))의 합  루프반복회수 * body의 실행시간 최대치 (1) for i:= 1 to n-1 (2) for j:= n downto i+1 (3) if A[j-1] > A[j] then begin (4) temp := A[j-1] (5) A[j-1] := A[j] (6) A[j]:= temp end (4)-(6) : O(1) (3)-(6) : O(1) (2)-(6) : O((n-i)*1) (1)-(6) : n(n-1)/2

Computing asymptotic complexity (1) Determine the complexity of each statement (2) Take the maximum (ex)

배열 배열정의 : a set of pairs (index and value) 배열 연산 : retrieve, store 배열표현 : 순차표현, 링크표현 메모리표현 : Row major order, Column major order 패턴매칭 정의, 패턴매칭알고리즘 분석 간단한 알고리즘 : O(nm) KMP 알고리즘 : O(n+m) BM 알고리즘 : O(n+m)

스택과 큐 스택 정의 : 삽입과 삭제가 top에서만 행해지는 순서 리스트 특성 : LIFO 연산 : add, delete 응용 : recursive call, interrupt, arithmetic expression, subroutine call and return, syntactic analyzer 큐의 정의 : 삽입이 rear에서 행해지고 삭제가 front에서 일어나는 순서리스트 특성 : FIFO 응용 : multiprocessing, CPU scheduling, Job scheduling 식의 평가 : Infix의 postfix로의 변환

링크 리스트 linear list(선형 리스트) : 순서가 있는 리스트 sequential list(순서 리스트) : 순서대로 저장                                  논리적 순서와 물리적 순서가 일치 linked list(연결 리스트) : 순서와 무관하게 저장(link로 순서 유지)                              논리적 순서와 물리적 순서가 불일치 nonlinear(비선형 리스트) : 순서를 정할 수 없는 리스트        tree(트리) : 계층적 리스트        graph(그래프) : 비계층적 리스트 순서리스트의 표현 : 순차표현 vs. 링크표현 스택과 큐의 링크 리스트 표현(알고리즘) 동치관계 Single linked list와 doubly linked list의 장단점