시스템 생명 주기(System Life Cycle)(1/2) 요구사항(requirements) 프로젝트들의 목적을 정의한 명세들의 집합 입력과 출력에 관한 정보를 기술 분석(analysis) 문제들을 다룰 수 있는 작은 단위들로 나눔 상향식(bottom-up)/하향식(top-down) 접근 방법 설계(design) 추상 데이타 타입(abstract data type) 생성 알고리즘 명세와 설계 기법 고려

시스템 생명 주기(2/2) 정제와 코딩(refinement and coding) 검증(verification) 데이타 객체에 대한 표현 선택 수행되는 연산에 대한 알고리즘 작성 검증(verification) 정확성 증명(correctness proof) 수학적 기법들을 이용해서 증명 테스트(testing) 프로그램의 정확한 수행 검증 프로그램의 성능 검사 오류 제거(error removal) 독립적 단위로 테스트 후 전체 시스템으로 통합

포인터와 메모리 할당(1/3) 포인터 C언어에서는 어떤 타입 T에 대해 T의 포인터 타입이 존재 포인터 타입의 실제값은 메모리 주소가 됨 포인터 타입에 사용되는 연산자 & : 주소 연산자 * : 역참조(간접 지시) 연산자 Ex) i(정수 변수), pi(정수에 대한 포인터) int i, *pi pi = &i; i에 10을 저장하기 위해서는 다음과 같이 할 수 있다. i = 10; 또는 *pi = 10; 널포인터 정수 0값으로 표현 널포인터에 대한 검사 int (pi ==Null) 또는 if(!pi)

포인터와 메모리 할당(2/3) 동적 메모리 할당 프로그램을 작성할 당시 얼마나 많은 공간이 필요한지 알수 없을때 사용 히프(heap) 기법 새로운 메모리 공간이 필요할 때마다 함수 malloc을 호출해서 필요한 양의공간을 요구 int i, *pi; float f, *pf; pi = (int *) malloc(sizeof(int)); pf = (float *) malloc(sizeof(float)); *pi = 1024; *pf = 3.14; printf(“an integer = %d, a float = %f\n”, *pi, *pf); free(pi); free(pf); 메모리 할당과 반환

포인터와 메모리 할당(3/3) 포인터의 위험성 포인터가 대상을 가리키고 있지 않을때는 값을 전부 null로 정하는 것이 바람직 이는 프로그램 범위 밖이나 합당하지 않은 메모리 영역을 참조할 가능성이 적어짐 명시적인 타임 변환(type cast) pi = malloc(sizeof(int)); /* pi에 정수에 대한 포인터를 저장 */ pf = (float *) pi; /* 정수에 대한 포인터를 부동소수에 대한 포인터로 변환 */

알고리즘 명세(1/9) 알고리즘(Algorithm) 특정한 일을 수행하기 위한 명령의 유한 집합 조건 입력 : (외부) 원인 ≥ 0 출력 : 결과 ≥ 1 명백성(definiteness) : 모호하지 않은 명확한 명령 유한성(finiteness) : 종료 유효성(effectiveness) : 기본적, 실행가능 명령 Ex) program ≡ algorithm 흐름도(flowchart) ≡ algorithm (명백성과 모호성에 결여)

알고리즘 명세(2/9) 예제[선택 정렬] : n ≥ 1개의 서로 다른 정수를 정렬 정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓음 정수들이 배열(array), list에 저장 i번째 정수는 list[i], 1≤ i ≤ n에 저장 최소 정수를 찾는 작업 최소 정수가 list[i]라 가정 List[i]와 list[i+1]~list[n-1] 비교 더 작은 정수를 만나면 새로운 최소정수로 선택 for ( i = 0; i < n; i++) { list[i]에서부터 list[n-1]까지의 정수값을 검사한 결과 list[min]이 가장 작은 정수 값이라 하자; list[i]와 list[min]을 서로 교환; } < 선택 정렬 알고리즘 >

알고리즘 명세(3/9) 최소 정수 값을 list[i] 값과 교환하는 작업 함수 정의 : swap(&a, &b) 매크로 정의 #define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t)) Void swap(int *x, int *y) /* 매개 변수 x, y는 정수형을 갖는 포인터 변수이다. */ { int temp = *x; /* temp변수를 int로 선언하고 x가 가르키는 주소의 내용을 지정한다. */ *x = *y /* y가 가리키는 주소의 내용을 x가 가리키는 주소에 저장한다. */ *y = temp /* temp의 내용을 y가 가리키는 주소에 저장한다. */ < swap 함수 >

알고리즘 명세(4/9) #include <stdio.h> #include <math.h> #define MAX_SIZE 101 #define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t)) void sort(int [], int); /* selection sort */ void main(void) { int i, n; int list[MAX_SIZE]; printf(“Enter the number of numbers to generate: ”); scanf(“%d”, &n); if(n<1 || n> MAX_SIZE) { fprintf(stderr, “Improper value of n\n”); exit(EXIT_FAILURE); } for (i=0; i<n; i++) { /* randomly generate numbers*/ list[i] = rand()%1000; printf(“%d”, list[i]);

알고리즘 명세(5/9) sort(list, n); printf(“\n Sorted array:\n”); for(i=0; i<n; i++) /*print out sorted numbers */ printf(“%d”, list[i]); printf(“\n”); } void sort(int list[], int n) { int i, j, min, temp; for(i=0; i<n-1; i++) { min = i; for (j = i+1; j<n; j++) if(list[j] <list[min]) min =j; SWAP(list[i], list[min], temp);

알고리즘 명세(6/9) 정리 1.1 증명 함수 Sort(list, n)는 n≥1개의 정수를 정확하게 정렬한다. 그 결과는 list[0], …, list[n-1]로 되고 여기서 list[0]≤list[1] ≤ list[n-1]이다. 증명 i=q에 대해, 외부 for 루프가 완료되면 list[q] ≤ list[r], q<r<n 이다. 다음 반복에서는 i>q 이고 list[0]에서 list[q]까지는 변하지 않는다. 따라서 바깥 for 루프를 마지막으로 수행하면(즉, i=n-2), List[0] ≤ list[1]≤... ≤ list[n-1]가 된다.

알고리즘 명세(7/9) 예제[이진탐색]: 정수 searchnum이 배열 list에 있는지 검사 List[0] ≤ list[1] ≤... ≤ list[n-1] 주어진 정수 searchnum에 대해 list[i]=searchnum인 인덱스 i를 반환 없는 경우는 -1 반환 초기값 : left=0, right=n-1 List의 중간 위치 : middle=(left+right)/2 List[middle]와 searchnum을 비교 1) searchnum < list[middle] : list[0] ≤ searchnum ≤ list[middle-1] right = middle-1 2) searchnum = list[middle] : middle을 반환 3) searchnum > list[middle] : list[middle+1] ≤ searchnum ≤ list[n-1] left = middle+1

알고리즘 명세(8/9) while (there are more integers to check) { middle = (left + right) / 2; if(searchnum < list[middle]) right = middle-1; else if (searchnum = = list[middle]) return middle; else if = middle +1; } < 정렬된 리스트 탐색 > int compare(int x, int y) { /* compare x and y, return -1 for less than, 0 for equal, 1 for greater */ if (x<y) return -1; else if (x = = y) return 0; else return 1; } < 두 정수의 비교 >

알고리즘 명세(9/9) 비교 연산 : 함수, 메크로 첫번째 수치 값이 두번째 수치의 값보다 작을때 음수 반환 두 수치 값이 같은 경우 0을 반환 첫번째 수치 값이 두번째 수치 값보다 큰 경우 양수 반환 #define COMPARE(x, y) ((x)<(y) ? -1 : (x) = =(y)) ? 0 : 1) int binsearch(int list[], int searchnum, int left, int right) { */ search list [0] <= list[1] <= … <= list[n-1] for searchnum. Return its position if found. Otherwise return -1 */ int middle; while (left <=right) { middle = (left + right) / 2; switch (COMPARE(list[middle], searchnum)) { case -1: left = middle + 1 break; case 0 : return middle; case 1 : right = middle -1;} } return -1;

순환 알고리즘(1/4) 수행이 완료되기 전에 자기 자신을 다시 호출 Fibonacci 수, factorial, 이항 계수 직접 순환 : direct recursion 간접 순환 : indirect recursion Fibonacci 수, factorial, 이항 계수

순환 알고리즘(2/4) 예제 [이진 탐색] int binsearch(int list[], int searchnum, int left, int right) { */ search list [0] <= list[1] <= … <= list[n-1] for searchnum. Return its position if found. Otherwise return -1 */ int middle; if (left <=right) { middle = (left + right) / 2; switch (COMPARE(list[middle], searchnum)) { case -1: return binsearch(list, searchnum, middle+1, right); case 0 : return middle; case 1 : return binsearch(list, searchnum, left, middle-1); } return -1; < 이원탐색에 대한 순환 구현 >

순환 알고리즘(3/4) 예제[순열] : n≥1개의 원소를 가진 집합 모든 가능한 순열 {a, b, c} : {(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)} N원소 : n!개의 상이한 순열 {a, b, c, d} 1) a로 시작하는 {b,c,d}의 모든 순열 2) b로 시작하는 {a,c,d}의 모든 순열 3) c로 시작하는 {a,b,d}의 모든 순열 4) d로 시작하는 {a,b,c}의 모든 순열

순환 알고리즘(4/4) 초기 함수 호출 : perm(list, 0, n-1) void perm(char *list, int i, int n) {*/ generate all the permutations of list[i] to list[n] */ int j, temp; if(I = = n) { for(j=0; j<=n; j++) printf(“%c”, list[j]); printf(“ ”); } else { /* list[i] to list[n] has more than one permutation, generate these recursively*/ for(j=I, j<=n; j++){ SWAP(list[i], list[j], temp); perm(list, i+1, n); < 순환 순열 생성기 >

데이터 추상화(1/4) C언어의 기본 자료형 : char, int, float, double 키워드 : short, long, unsigned 자료의 그룹화 : 배열(array), 구조(stucture) Int list[5] : 정수형 배열 구조 포인터 자료형 : 정수형, 실수형, 문자형, float형 포인터 int i, *pi; 사용자 정의(user-defined) 자료형 struct student { char lastName; int studentId; char grade; }

데이터 추상화(2/4) 정의 : 자료형 타입(data type) 객체(object)와 그 객체위에 작동하는 연산(operation)들의 집합 int : {0, +1, -1, +2, -2, …, INT_MAX, INT_MIN} 정수 연산 : +, -, *, /, %, 테스트 연산자, 치환문 … atoi와 같은 전위(prefix) 연산자 +와 같은 중위(infix) 연산자 연산: 이름, 매개 변수, 결과가 명세 자료형의 객체 표현 char형: 1바이트 비트 열 int형: 2 또는 4바이트 구체적인 내용을 사용자가 모르도록 하는 것이 좋은 방법 객체 구현 내용에 대한 사용자 프로그램의 독립성

데이터 추상화(3/4) 정의 : 추상 자료형(ADT: abstract data type) 객체의 명세와 그 연산의 명세가 그 객체의 표현과 연산의 구현으로부터 분리된 자료형 명세와 구현을 명시적으로 구분 Ada – package, C++ – Class ADT 연산의 명세 함수 이름, 매개 변수형, 결과형, 함수가 수행하는 기능에 대한 기술 내부적 표현이나 구현에 대한 자세한 설명은 필요 없음  ADT가 구현에 독립 자료형의 함수 생성자(creater)/구성자(constructor) : 새 인스턴스 생성 변환자(transformer) : 한 개 이상의 서로 다른 인스턴스를 이용하여 지정된 형의 인스턴스를 만듬 관찰자(observers)/보고자(reporter) : 자료형의 인스턴스에 대한 정보를 제공

데이터 추상화(4/4) 예제[추상 데이터 타입 NaturalNumber] 객체(objects) : 0에서 시작해서 컴퓨터상의 최대 정수값 (INT_MAX)까지 순서화된 정수의 부분 범위이다. 함수(functions) : for all x, y ∈ Nat_Number, TRUE, FALSE ∈ Boolean에 대해, 여기서 +, -, <, 그리고 ==는 일반적인 정수 연산자이다. NaturalNumber Zero() ::= 0 Boolean IsZero(x) ::= if(x) return FALSE else return TRUE Boolean Equal(x, y) ::= if(x= =y) return TRUE else return FALSE NaturalNumber Successor ::= if(x = = INT_MAX) return x else return x+1 NaturalNumber Add(x,y) ::= if((x+y)<= INT_MAX) return x+y else return INT_MAX NaturalNumber Subtract(x,y) ::= if(x<y) return 0 else return x-y End NaturalNumber

성능 분석 성능 평가(performance evaluation) 정의 성능분석(performance analysis) 시간과 공간의 추산 복잡도 이론(complexity theory) 성능측정(performance measurement) 컴퓨터 의존적 실행 시간 정의 공간 복잡도(space complexity) 프로그램을 실행시켜 완료하는데 필요한 공간의 양 시간 복잡도(time complexity) 프로그램을 실행시커 완료하는데 필요한 컴퓨터 시간의 양

공간 복잡도(1/3) 프로그램에 필요한 공간 공간 요구량 : S(P) = c + Sp(I) 예제 : abc 고정 공간 요구 프로그램 입출력의 횟수나 크기와 관계없는 공간 요구 명령어 공간, 단순 변수, 고정 크기의 구조화 변수, 상수 가변 공간 요구 문제의 인스턴스, I, 에 의존하는 공간 가변 공간, 스택 공간 공간 요구량 : S(P) = c + Sp(I) 예제 : abc 고정 공간 요구만을 가짐  Sabc(I) = 0 float abc(float a, float b, float c) { return a+b+b*c + (a+b-c) / (a+b) + 4.00; }

공간 복잡도(2/3) [예제] sum 가변 공간 요구: 배열(크기 n) 함수에 대한 배열의 전달 방식 Pascal : 값 호출(call by value) Ssum(I) = Ssum(n) = n : 배열 전체가 임시기억장소에 복사 C : 배열의 첫번째 요소의 주소 전달 Ssum(n) = 0 float sum(float list[], int n) { float tempsum = 0; int i; for (i=0; i<n; i++) tempsum += list[i]; return tempsum; }

공간 복잡도(3/3) [예제] rsum 컴파일러가 매개 변수, 지역 변수, 매 순환 호출시에 복귀 주소를 저장 하나의 순환 호출을 위해 요구되는 공간 두개의 매개 변수, 복귀 주소를 위한 바이트 수 = 2(sizeof(n)) + 2(list[]의 주소) + 2(복귀주소) = 6 N = MAX_SIZE  Srsum(MAX_SIZE) = 6 * MAX_SIZE float rsum(float list[], int n) { int (n) return rsum(list, n-1) + list[n-1]; return 0; }

시간 복잡도(1/7) 프로그램 P에 의해 소요되는 시간 : T(P) = 컴파일 시간 + Tp(= 실행 시간) Tp(n) = CaADD(n) + CsSUB(n) + ClLDA(n) + CstSTA(n) - Ca, Cs, Cl, Cst : 각 연산을 수행하기 위해 필요한 상수 시간 - ADD, SUB, LDA, STA(n) : 특성 n에 대한 연산 실행 횟수 정의 : 프로그램 단계(program step) 실행 시간이 인스턴스 특성에 구문적으로 또는 의미적으로 독립성을 갖는 프로그램의 단위 a = 2 a = 2*b+3*c/d-e+f/g/a/b/c ※ 한단계 실행에 필요한 시간이 인스턴스 특성에 독립적이어야 함  1 step!!

시간 복잡도(2/7) 단계의 계산(방법 1) 예제[리스트에 있는 수의 반복적 합산] 전역 변수 count의 사용 float sum(float list[], int n) { float tempsum = 0; count++; /*for assignment */ int i; for(i=0; i<n; i++) { count++; /*for the for loop */ tempsum += list[i]; count++; /*for assignment */ } count++; /* last execution of for */ count++; /* for return */ return tempsum; float sum(float list[], int n) /* 단순화된 프로그램 */ { float tempsum = 0; int i; for(i=0; i<n; i++) count += 2; count += 3; return 0; }

시간 복잡도(3/7) 예제[리스트에 있는 수의 순환적 합산 n = 0  2(if, 마지막 return) n > 0  2(if, 처음 return) : n회 호출 ∴ 2n + 2 steps ※ 2n + 3 (iterative) > 2n + 2 (recursive)  Titerative > Trecursive float sum(float list[], int n) { count++; /*for if conditional */ if (n) { count++; /*for return and rsum invocation */ return rsum(list, n-1) + list[n-1]; } count++; return list[0];

시간 복잡도(4/7) 예제[행렬의 덧셈] void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE}, int rows, int cols) { int i, j; for(i=0; i<rows; i++) for(j=0; j<cols; j++) c[i][j] = a[i][j] + b[i][j]; } void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE}, int rows, int cols) { int i, j; for(i=0; i<rows; i++) { count++; /* for i for loop */ for(j=0; j<cols; j++) { count++; /* for j for loop */ c[i][j] = a[i][j] + b[i][j]; count++; } /* for assignment statement */ count++; /* last time of j for loop */ } count++; /*last time of i for loop */ < count문이 첨가된 행렬의 덧셈 >

시간 복잡도(5/7) 배열 크기 = rows  cols 단계수 = 2rows · cols + 2rows + 1 void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE}, int rows, int cols) { int i, j; for(i=0; i<rows; i++) for(j=0; j<cols; j++) { count += 2; count+=2; } count++;

시간 복잡도(6/7) 단계의 계산(방법 2) [예제] 리스트에 있는 수를 합산하는 반복함수 테이블 방식(tabular method) : 단계수 테이블 문장에 대한 단계수 : steps/execution, s/e 문장이 수행되는 횟수 : 빈도수(frequency) 비실행 문장의 빈도수 = 0 총 단계수 : 빈도수  s/e [예제] 리스트에 있는 수를 합산하는 반복함수 문 장 s/e 빈도수 총단계수 float sum(float list[], int n) { float tempsum = 0; int i; for (i=0; i<n; i++) tempsum += list[i]; return tempsum; } 0 0 0 1 1 1 1 n+1 n+1 1 n n 합 계 2n+3

시간 복잡도(7/7) [예제] 리스트에 있는 수를 합산하는 순환 함수 [예제] 행렬의 덧셈 문 장 s/e 빈도수 총단계수 문 장 s/e 빈도수 총단계수 float rsum(float list[], int n) { if (n) return rsum(list, n-1) + list[n-1] return list[0]; } 0 0 0 1 n+1 n+1 1 n n 1 1 1 합 계 2n+2 문 장 s/e 빈도수 총단계수 void add(int a[][MAX_SIZE] ··· ) { int i, j; for (i=0, i<rows; i++) for(j=0, j<cols; j++) c[i][j] = a[i][j] + b[i][j] } 0 0 0 1 rows+1 rows+1 1 rows(cols+1) rows·cols+row 1 rows·cols rows·cols 합 계 2rows·cols+2rows+1

점근 표기법(O,Ω,Θ )(1/10) Worst case step count : 최대 수행 단계수 Average step count : 평균 수행 단계수  동일 기능의 두 프로그램의 시간 복잡도 비교 인스턴스 특성의 변화에 따른 실행 시간 증가 예측 정확한 단계의 계산 : 무의미 A의 단계수 = 3n + 3, B의 단계수 = 100n +10  TA << TB A ≈3n(or 2n), B ≈100n(or 80n, 85n)  TA << TB 근사치 사용 C1과 C2가 음이 아닌 상수일때 C1n2 ≤ TP(n) ≤ C2n2 또는 TQ(n,m) = C1n + C2m 예) C1=1, C2=2, C3=100 C1n2 + C2n ≤ C3n, n ≤ 98 C1n2+C2n > C3n, n > 98 균형분기점(break even point) : n = 98

점근 표기법(2/10) 정의 [Big “oh”] 예제 모든 n, n≥no에 대해 f(n)≤cg(n)인 조건을 만족하는 두 양의 상수 c와 no가 존재하기만 하면 f(n)=O(g(n))이다. 예제 n≥2, 3n+2≤4n  3n+2=O(n) n≥3, 3n+3≤4n  3n+2=O(n) n≥10, 100n+6≤101n  3n+2=O(n) n≥5, 10n2+4n+2≤11n2  3n+2=O(n) n≥4, 6*2n+n2≤7*2n  3n+2=O(n) n≥2, 3n+3≤3n2  3n+2=O(n) n≥2, 10n2+4n+2≤10n4  3n+2=O(n) n≥n0인 모든 n과 임의의 상수 c에 대해 3n+2≤c가 false인 경우가 존재하면 3n+2≠O(1), 10n2+4n+2 ≠O(n) ※ O(1)< O(log n)< O(n)< O(n logn)< O(n2)< O(n3)< O(2n) ※ f(n) = O(g(n)) n≥ n0인 모든 n에 대해 g(n) 값은 f(n)의 상한값 g(n)은 조건을 만족하는 가장 작은 함수여야 함

점근 표기법(3/10) 정의 [Omega][f(n) = Ωg(n)] 예제 모든 n, n≥n0에 대해서 f(n)≥ cg(n)을 만족하는 두 양의 상수 c와 n0가 존재하기만 하면 f(n) = Ω(g(n))이다. 예제 n≥1, 3n+2 ≥ 3n  3n+2 = Ω(n) n≥1, 3n+3 ≥ 3n  3n+3 = Ω(n) n≥1, 100n+6 ≥ 100n  100n+6 = Ω(n) n≥1, 10n2+4n+2 ≥ n2  100n2+4n+2 = Ω(n2) n≥1, 6*2n+n2 ≥ 2n  6*2n+n2 = Ω(2n) ※g(n) : f(n)의 하한 값(가능한 큰 함수)

점근 표기법(4/10) 정의[Theta][f(n) = Θ(g(n))] 예제 모든 n, n≥n0에 대해서 C1g(n)≤ f(n) ≤ C2g(n)을 만족하는 세 양의 상수 C1, C2와 n0가 존재하기만 하면 f(n)=Θ(g(n))이다. 예제 n ≥ 2, 3n ≤ 3n+2 ≤ 4n  3n+2 = Θ(n) c1=3, c2=4, n0=2 3n+3= Θ(n) 10n2+4n+2 = Θ(n2) 6*2n+n2 = Θ(2n) 10*log n + 4 = Θ(log n) ※g(n)이 f(n)에 대해 상한 값과 하한 값을 모두 가지는 경우 ※g(n)의 계수는 모두 1

점근 표기법(5/10) 예제 점근적 복잡도(asymptotic complexity: O, Ω, Θ)는 Tsum = 2n + 3  Tsum(n) = Θ(n) Trsum(n) = 2n + 2  Θ(n) Tadd(rows, cols) = 2row·cols + 2rows + 1 = Θ(rows·cols) 점근적 복잡도(asymptotic complexity: O, Ω, Θ)는 정확한 단계수의 계산없이 쉽게 구함 예제[행렬 덧셈의 복잡도] 문 장 점근적 복잡도 void add(int a[][MAX_SIZE] ··· ) { int i, j; for (i=0, i<rows; i++) for(j=0, j<cols; j++) c[i][j] = a[i][j] + b[i][j] } Θ(rows) Θ(rows·cols) 합 계

점근 표기법(6/10) [예제] 이원탐색 이원 탐색 함수(binsearch)에서 시간 복잡도 구하기 while 루프에서 반복시간 : log2(n+1)번 매 반복 실행은 탐색되어야 할 list 세그먼트의 크기를 절반으로 감소  최악의 경우 Θ(log n)번 반복 한번 반복 실행하는데 Θ(1)의 시간이 걸리기 때문에 binsearch의 최악의 경우 복잡도는 Θ(log n) ※유의할 것은 while 루프의 첫번째 반복 실행에서 searchnum을 찾는 경우는 최상의 경우로서 복잡도가 Θ(1)이 되는것임

점근 표기법(7/10) [예제] 순열 i=n일때 걸리는 시간 : Θ(n) i<n일때 else절 수행 for루프는 n-i+1번 수행 루프를 한번 실행할때 마다 Θ(n+ Tperm(i+1, n))시간 소요 i<n일때 Tperm(i, n) = Θ((n-i+1)(n+Tperm(i+1,n))) Tperm(i+1,n)는 i+1≤n일때 적어도 n이기 때문에 i<n에 대해 Tperm(i, n) = Θ((n-i+1)Tperm(i+1, n))을 얻음 이 순환을 풀면 n≥1에 대해 Tperm(i, n) = Θ(n(n!))라는 결론

점근 표기법(8/10) [예제] 매직 스퀘어 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11 < n=5인 매직 스퀘어 > #include <stdio.h> #define MAX_SIZE 15 /*maximum size of square */ Void main(void) { /* construct a magic square, iteratively */ int square[MAX_SIZE][MAX_SIZE]; int i, j, row, column; /* indexes * / int count; /* counter */ int size; /* square size */ printf(“Enter the size of the square: ”); scanf(“%d”, &size); /* check for input errors */

점근 표기법(9/10) if (size <1 || size > MAX_SIZE +1) { fprintf(stderr, “Error! Size is out of range\n”) exit(EXIT_FAILURE); } if (!(size %2)) { fprintf(stderr, “Error! Size is even\n”); for (i=0; i<size; i++) for(j=0; j<size; j++) square[i][j] = 0; square[0][(size-1) / 2] = 1; /* middle of first row */ /* i and j are current position */ i = 0; j = (size-1) /2; for(count = 2; count <= size *size; count++) { row = (i-1<0) ? (size - 1) : (i-1); /*up*/ column = (j-1<0) ? (size-1) : (j-1); /*left*/

점근 표기법(10/10) if(square[row][column]) /*down*/ i = (++i) %size; else { /*square is unoccupied */ i = row; j = (j-1<0) ? (size -1) : --j; } square[i][j] = count; /* output the magic square */ printf(“Magic Square of size %d : \n\n”, size); for (i=0; i<size; j++) { for (j=0; j<size; j++) printf(“%5d”, square[i][j]); printf(“\n”) printf(“\n\n”); < magic square 프로그램 >

실용적인 복잡도 함수값 log n n n log n n2 n3 2n 1 2 4 8 16 64 3 24 512 256 4,096 요구되는 단계 수는 대략 1.1*1012 1초에 10개의 단계를 수행하는 컴퓨터라면 약 18.3분 요구 n=50 이면 13일, n=60 이면 310.56년, n=100 이면 4*1013년  따라서 유용도는 n이 아주 작을때(n≤40)로 제한됨 log n n n log n n2 n3 2n 1 2 4 8 16 64 3 24 512 256 4,096 65,536 5 32 160 1024 32,768 4,294,967,296

성능 측정(1/6) 시간측정 방법 1: clock을 사용 방법 2: time을 사용 방법 1 방법 2 시작시간 start = clock(); start = time(NULL); 종료시간 stop = clock(); stop = time(NULL) 반환타입 clock_t time_t 초 단위 결과 Duration = ((double)(stop-start))/ CLOCKS_PER_SEC duration = (double) difftime(stop, start); < C 에서 시간을 재는 사건 >

성능 측정(2/6) [예제] 선택 함수의 최악의 성능 #include <stdio.h> #include <time.h> #include “selectionSort.h” #define MAX_SIZE 1001 void main(void) { int i, n, step = 10; int a[MAX_SIZE]; double duration; clock_t start; /* time for n = 0, 10, …., 100, 200, …., 1000 */ printf(“ n time\n”); for(n=0; n<= 1000; n += step) /* get time for size n */

성능 측정(3/6) /* initialize with worst-case data */ for (i=0; i<n; i++) a[i] = n-1; start = clock(); sort(a, n); duration = ((double)) (clock() – start)) / CLOCK_PER_SEC; printf(“%6d %f\n”, n, duration); if (n ==100) step = 100; } < 선택 정렬 함수의 첫번째 시간 측정 프로그램 >

성능 측정(4/6) #include <stdio.h> #include <time.h> #include “selectionSort.h” #define MAX_SIZE 1001 void main(void) { int i, n, step = 10; int a[MAX_SIZE]; double duration; /* time for n = 0, 10, …., 100, 200, …., 1000 */ printf(“ n time\n”); for(n=0; n<= 1000; n += step) /* get time for size n */ long repetitions = 0; clock_t start = clock( ); do

성능 측정(5/6) { /* initialize with worst-case data */ for (i=0; i<n; i++) a[i] = n – i; sort(a, n); } while (clock( ) – start < 1000); /* repeat until enough time has elapsed */ duration = ((double) (clock() - start)) / CLOCK_PER_SEC; duration /= repetitions; printf(“%6d %9d %f \n”), n repetitions, duration); if (n ==100) step = 100; } < 보다 정확한 선택 정렬 함수의 시간 측정 프로그램 >

성능 측정(6/6) n repetitions time 8690714 0.000000 100 44058 0.000023 10 8690714 0.000000 100 44058 0.000023 10 2370915 200 12585 0.000079 20 604948 0.000002 300 5780 0.000173 30 329505 0.000003 400 3344 0.000299 40 205605 0.000005 500 2096 0.000477 50 145353 0.000007 600 1516 0.000660 60 110206 0.000009 700 1106 0.000904 70 85037 0.000012 800 852 0.001174 80 65751 0.000015 900 681 0.001468 90 54012 0.000019 1000 550 0.001818 < 선택 정렬의 최악의 경우에서의 성능(단위는 초) >