이 책은 1983 채택된 ANSI C를 사용했다고 한다..(preface)
1.1 OVERVIEW : SYSTEM LIFE CYCLE
data abstraction, algorithm specification, performance analysis and measurement의 확고한 기초를 잡는건 필수이다.
좋은 프로그래머는 큰 프로그램을 많은 복잡한 부분들이 서로 상호작용하는 system으로 본다.
이런 프로그램(system)은 system life cycle이란 프로그램 개발 단계를 거친다.
(왜 life cycle이라고 하지.. 뭔 의민가했네)
단계별로 설명해보자면..(각 단계는 closely interrelated)
system life cycle
-
Requirements
: 큰 프로그램 프로젝트는 해당 project의 purpose를 기술하는 specification을 처음에 작성해야한다.
Input이나 Output에 대한 설명도 작성해야한다.
대게 초반 specification은 모호하게 기술될 수 있어서, Input/Output case 같은걸 철저하게 모두 작성해야한다. -
Analysis
: After delineate Requirements carefully, "analysis" 단계로 넘어온다.
analysis에는 두가지 방법이 있다. (1)bottom-up, (2)top-down
(여기서 말한 C/C++ 차이에서의 topdown, bottomup과는 다른 얘기다.)
(1) bottom-up 분석 방식이 더 오래됐는데, 미세한 점을 초반에 더 강조하는 strategy. project의 master plane이 없기때문에 연결성이 떨어지고, 에러가 잘 나타날 수 있다.
건물을 일반적인 청사진으로 짓는거나 마찬가지다.(즉, 모든 건물을 똑같이 지음..)
그런데도 초보들은 흔히 초기계획 없이 error 없는 좋은 프로그램을 만들 수 있다고 생각한다.
(2) top-down 분석 방식은 프로그램을 관리하기 쉬운 segments로 나눈다. 프로그램을 design하기위해 diagram을 사용하고, 대안해결책도 자주 나온다. -
Design
: Analysis 이후에 두가지 관점으로 디자인을 할 수 있다.
(1)data object와 (2)그 data object에 할 수 있는 operation.
첫번째 관점으로부터 ADT(Abstract Data Type)을 만들고, 두번째 관점으로부터 algorithms specification을 만들어낸다.
예를들어 대학의 scheduling system을 만든다고 하면, ADT에는 학생, 강의, 교수님들 같은게 올 수 있고, search나 add 같은 operation을 수행할 수 있다.
ADT나 algorithm specification은 language independent이기 때문에 자세한 구현은 나중에 한다.
즉, data object에 대한 기술은 자세하게 하지만 coding detail은 일단 무시한다.(나중에 보겠지만, 자료 저장 방법이 array, linked-list, tree 등등 있음) -
Refinement and Coding
: data object를 어떻게 표현할지 고르고, 각 operation의 algorithms을 작성한다.
순서가 중요한데, data object의 표현법에 따라 관련된 algotihms의 효율성이 좌우되기 때문이다.
그래서 data object와 독립적인 algorithms을 먼저 작성해야한다.
자주 이 단계에서 더 나은 system을 만들 수 있다고 깨닫는데(대안 디자인이 더 낫다거나..), 그래서 미리 coding details을 작성하는걸 피한 것이다.
더 나은 프로그램을 원한다면 바꾸는 것을 주저하면 안된다. -
Verification
: correctness proof,
testing(with a variety of input data),
removing errors
로 이루어진다.
이 부분에 대한 연구는 광범위하게 이루어지고, 모든걸 다 말하는건 이 책 범위를 벗어나기때문에 중요한 부분만 요약했다.
correctness proof : 수학에서 쓰는 기법을 사용해서 증명하는데, but 시간이 좀 걸리고, 큰 project엔 좋지않다.(scheduling 제약 때문에 주로 막힌다고 함)
하지만 정확하다고 증명된 알고리즘은 error 줄이는데 도움이 될 수 있어서 그걸 이 책에서 제공해준다고 하네.. 언제알려줄라나
Testing : corretness proof는 특정 언어로 작성될 필요가 없는 coding단계 전에(혹은 중에) 사용할 수 있다.
하지만 testing은 작동하는 code와 test data가 필요하다. 그 test data는 모든 경우의 수를 포함할 수 있도록 신중하게 골라야한다.
초보들은 대게 syntax error만 없으면 한가지 정도의 test data가지고 프로그램이 correct할거라고 생각한다.
하지만 좋은 test data라면 모두 포함해야한다.(만약 switch statement가 있다면 switch의 모든 case를 볼 수 있게..)
처음에는 error를 없애는게 목적이겠지만, running time 또한 중요한 요소이다.
Error removal : correctness proof와 testing을 통해 error을 표시할 수 있을 것이다.
spaghetti code라면 에러를 고칠때마다 또 에러가 발생할 수 있어서 처음부터 coding을 잘했어야한다.
각 unit이 parameter로 interact하며 well documented돼있어야한다. 그럼 각 unit을 따로 test하고 나중에 합쳐지도록 할 수 있다.
1.2 POINTERS AND DYNAMIC MEMORY ALLOCATION
malloc 함수는 자주 쓰이기 때문에, 함수 호출과 NULL pointer인지 test하는 것은 macro로 정의해놓는게 편하다.
#define MALLOC(p,s) \
if(!((p) = malloc(s))) { \
fprintf(stderr, "Insufficient memory"); \
exit(EIXT_FAILURE); \
}p에 괄호 붙이는거 잊지말자(기억안나면 knk 14.3)
그리고 <stdilb.h> include 해야함공간이 필요없으면 free로 deallocate해서, dangling reference 문제를 없애야한다.
free안하고 그냥 해당 포인터가 다른 공간을 가리키게 해버리면 그 공간은 덩그러니 남아있게 된다.
주의
1. pointer를 사용하지 않을땐 NULL pointer로 해두면좋다.
2. pointer type끼리 변환할때 casting해주는게 좋다.
1.3 ALGORITHM SPECIFICATION
1.3.1 INTRODUCTION
Algorithm은 CS의 기초이다. 공통된 문제를 효율적인 algorithms으로 해결함으로써 규모가 큰 computer system을 개발할 수 있다.
그래서 일단 이 개념을 잘 잡고 가야한다.
Definition : An algorithm is a finite set of instructions that, if followed, accomplishes a particular task.
모든 algorithm은 아래 기준을 만족해야한다.
1. Input : 외부로부터 0개 이상 input
2. Output : 최소 1개의 output이 나와야 한다.
3. Definiteness : 각 instructions은 명확하고, 모호하지 않아야된다.
4. Finiteness : algorithm의 instructions을 따라가면, 모든 case에 대해 유한한 step을 거쳐 종료돼야한다.
5. Effectiveness : 모든 instructions은 원칙적으로 종이와 펜 만으로도 수행될 수 있을 정도로 기본적이어야한다. 각 operation이 (3)처럼 명확하기만 해선 안되고 실현가능(feasible)하기까지 해야한다.
computation 이론에서 algorithm과 program의 차이는, program은 4번째 조건을 만족하지 않아도 된다는 것이다.
OS를 예로 보면 그렇다, 작업이 입력될때까지 wait loop 내에서 기다리고, crash되지 않는 이상 종료되지 않는다.
하지만 우리가 만드는 program은 종료되기 때문에, 그런 맥락에선 algorithm과 program을 같이 쓸 수 있다.
algorithm을 표현할 수 있는 방법은 많다. 우리가 쓰는 영어나 한글로도 이를 표현할 수 있는데, 이런 경우 4번 finiteness를 유의해야한다. flowchart라는 것도 있는데 이는 간단한 알고리즘만 표현할 수 있다.
이 책에서는 C언어로 algorithm을 표현한다.(혹은 가끔 english 섞어서)
Example 1.1
selection sort
(sort할때 나올줄 알았는데 안나오길래 정리하고 가는게 맞지싶네)
algorithm을 언어로 작성할때는 명확하게 작성해야한다.
sort problem에 대해 알고리즘을 작성한다고하면
: "From those integers that are currently unsorted, find the smallest and place it next in the sorted list."
라고 하면 대충 설명은 되지만 명확하지 않다. 뭐 값을 어디에 저장할건지.. 등등
그래서 C로 표현하면 명확하게 할 수 있다.
(SWAP macro 잘 봐두자, 함수로 만들어도 되지만 그럼 type generic이 안된다.)
Selection Sort : 리스트에서 최솟값을 찾고, 해당 값과 제일 앞의 값을 바꾼다. 제일 앞을 뺀 나머지 리스트에대해 같은 방법을 수행한다. 원소가 하나 남을때까지 반복한다.
//Selection Sort
#include <stdio.h>
#include <math.h> //rand함수 stdlib.h지 않나? 뭐어쨌든
#define MAX_SIZE 101
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int [], int); //selection sort
int main(void) { //책엔 return type void로 돼있는데, portability위해 int로 작성
int i, n;
int list[MAX_SIZE];
printf("Enter the number of numbers to generate: ");
scnaf("%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;
pritnf("%d ", list[i]);
}
sort(list, n); //sort
pritnf("\nsorted array: \n");
for(i = 0; i < n; i++) //print out sorted numbers
printf("%d ", list[i]);
printf("\n");
return 0;
}
void sort(int list[], int n) {
int min, temp;
for(int i = 0; i < n-1; i++) { //i는 index니까 n-1
min = i; //minimum의 index 저장
for(int j = i+1; j < n; j++)
if(list[j] < min)
min = j;
SWAP(list[i], list[j], temp);
}
}위 sort 함수가 올바르게 작동하는지 확인
(딱히 여기 정리할 필요가 있나.. 싶긴한데 처음 나온거니까 정리해보자.)
Theorem 1.1
: 함수 sort(list, n)은 n>=1개의 숫자에 대해 올바르게 작동한다. 결과는 list[0], ..., list[n-1]에 저장되고, list[0] <= list[1] <= ... <= list[n-1]이다.
Proof 1.1
: i = q일때 바깥 for문이 다 돌고나면, list[q] <= list[r](q<r<n)이다. 추가로 i>q인 나머지 loop에서 list[0]~list[q]는 변하지 않는다. 따라서 바깥 loop가 마지막으로 돌고 나면 list[0] <= list[1] <= ... <= list[n-1]인 list가 나온다.
Example 1.2
Binary search
(정렬된 list에서 특정 숫자 searchnum을 찾는 알고리즘)
left를 찾을 list의 제일 왼쪽값, right를 제일 오른쪽 값으로 설정한다.
middle을 (left+right)/2로 설정한다.
1) middle의 값이 찾고자 하는 값이라면, middle의 index를 반환한다.
2) middle의 값이 찾고자 하는 값보다 크다면, right를 middle - 1으로 설정하고 다시 search
3) middle의 값이 찾고자 하는 값보다 작다면, left를 middle + 1으로 설정하고 다시 search
search는 두가지 단계로 나누어진다.
1) 더이상 찾을 integer가 남았는지
2) 찾고자 하는 값과 list[middle]과의 비교
//binary search function
//left~right boundary에 searchnum이 있는지 검색, 있으면 position, 없으면 -1 반환
int binsearch(int list[], int searchnum, int left, int right) {
int middle;
while (left <= right) { //left==right인 경우까지 확인해봐야됨
middle = (left+right)/2
switch(COMPARE(list[middle], searchnum):
case -1: left = middle + 1;
break;
case 0: return middle; //return이라 break 필요 X
case 1: right = middle - 1;
}
return -1;
}COMPARE macro : #define COMPARE(x,y) (((x)<(y)) ? -1 : ((x)==(y)) ? 0 : 1)
주의 : middle은 (left-right)/2 아니다. 더해야한다.
1.3.2 Recursive Algorithms
자기 스스로 호출하는 함수(direct recursion)와 다른 함수로부터 또다시 호출되는 함수(indirect recursion)으로 나뉜다.
대부분 재귀함수를 특수한 경우(factorial 구할때 등)에만 사용한다고 생각하는데, if-else나 while만 있어도 recursive function으로 만들 수 있다.
그렇게 하는게 오히려 반복문이 있는 것보다 보기 쉬울 수 있다.
그럼 언제 재귀함수로 만들 것인가?
한 예시로, factorial이나 fibonacci number 혹은 binomial coefficient 같이 공식에 의해 재귀적으로 계산될 수 있는 경우 recursive하게 만들 수 있다.
binary search(recursive version)
//binary search function (recursive)
int binsearch(int list[], int searchnum, int left, int right) {
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;
}Permutation
{a,b,c,d}의 permutation이라면 아래 경우로 나뉜다.,
1) a 뒤에 {b,c,d}의 모든 permutation
2) b 뒤에 {a,c,d}의 모든 permutation
3) c 뒤에 {a,b,d}의 모든 permutation
4) d 뒤에 {a,b,c}의 모든 permutation
즉, n개 문자의 순열을 모두 나타내는 함수를 만들고자 한다면 n-1개의 순열을 모두 나타낼 수 있는 algorithm이 있으면 된다.
recursive로 구현할 수 있다.
아래 함수 호출할때는 : perm(list, 0, n-1); (i값을 0으로 준다.)
void perm(char *list, int i, int n) {
int j, temp;
if (i == n) {
for (j = 0; j <= n; j++)
printf("%c", list[j]);
printf(" ");
}
else {
for(j = i; j <= n; j++) {
SWAP(list[i],list[j],temp);
perm(list, i+1, n);
SWAP(list[i],list[j],temp);
}
}
}list랑 i는 재귀로 호출될때마다 값이 바뀐다. n은 바뀌지 않음.
https://stackoverflow.com/questions/7537791/understanding-recursion-to-generate-permutations
"user786653"이랑 "flight" 답변 보면 좋음
1.4 DATA ABSTRACTION
모든 programming language는 기본 data type을 제공하고, 사용자가 원하는 data type을 정의할 수 있도록 해준다.
DATA TYPE
DEFINITION
: A data type is a collection of (1)objects and a set of (2)operations that act on those objects.
간단한 int type만 봐도 그 type에 행할 수 있는 연산 +, -, =, == 등이 있다.
이렇게 opearation을 아는건 그렇다치고,
representation of the objects of a data type을 아는 것은 유용할수도, 위험할 수도 있다.
표현법을 앎으로써 algorithm을 작성할때 해당 data type을 잘 사용할 수 있지만, 반대로 objects의 representation을 바꾸고 싶을때 그 object를 사용한 모든곳을 바꿔야되는게 문제가 된다.
많은 software designer는 data type object의 representation을 사용자로부터 숨기는 것이 좋은 design 전략이라고 한다.
KNK:chapter19
그렇게 하면 representation을 바꾸더라도 user interface에선 변함이 없다. 즉 새로운 implementation으로 옮기더라도 algorithm을 다시 작성할 필요가 없어진다.
ABSTRACT DATA TYEP (ADT)
DEFINITION
: An abstract data type (ADT) is a data type that is organized in such a way the specification of the objects and the specification of the operations on the objects is sperated from the representation of the objects and the implementations of the operations.
(knk chapter 19에서 설명한 것보다 쪼끔더 general하게 얘기하네)
"specification"과 "implementation"의 차이는 무엇인가?
"specification"엔 모든 함수이름, 함수 argument type, return type, 함수 설명 같은게 올 수 있다.
하지만 internel representation이나 implementation detail은 포함하지 않는다.
즉, ADT는 implementation-independent이다.
specification과 implementation을 명확히 분리하는 mechanism을
다른 언어에선 지원하기도 하지만(C++의 경우 class),
C에는 명확한 mechanism이 없다.data type의 함수(기능)은 아래 category로 나뉘어진다.
1) Creator/constructor : 지정된 type의 새로운 instance를 만든다.
(p.20의 Zero 함수에 해당)
2) Transformers : 하나 이상의 다른 instance를 사용해 지정된 type의 새로운 instance를 만든다.
(p.20의 Successor 함수에 해당)
3) Observers/reporters : type의 instance에 대한 정보를 제공한다. instance를 변경하진 않는다.
보통 ADT는 위 세가지 중 적어도 한가지 종류의 function을 포함한다.
책에서 specification과 implementation의 차이를 강조하기 위해,
보통 ADT를 먼저 설명하겠다고 한다.
복잡한 implementation 대신.. ADT를 보고 먼저 이해하면 더 쉬울거라고 하네
ADT이기때문에 C와 당연히 차이가 있을 수 있고,
심지어 표현한 parameter에도 차이가 있을 수 있다.1.5 PERFORMANCE ANALYSIS
program에 대한 평가/판단 skill을 기르는 것도 이 책의 목표
program을 판단하는 여러 기준이 있는데,
'잘 작동하나?', 'code는 readable한가?' 같은 기준은 달성했는지 파악하기가 모호하다.
물론 이 또한 매우 중요한 기준이긴하지만, 이런건 많이 연습하면 늘 수 있는거니까 책 열심히 보시고,,
명확한 기준인
1)Performance analysis : machine independent인 time과 space에 대한 측정. complexity theory가 CS에서 중요한 개념이다.
2)Performance measurement : machine-dependent running time을 측정.
에 대해 알아보겠다.(여기 1.5에선 performance analysis)
Space complexity & Time complexity
DEFINITION
: The space complexity of a program is the amount of memory that it needs to run to completion. The time complexity of a program is the amount of computer time that it needs to run to completion.
1.5.1 Space complexity
program이 필요로하는 공간은 아래 두 요소의 총합이다.
1. Fixed space requirements : I/O에 영향을 받지않는 공간이다. instruction space(code 저장공간), 간단한 변수 저장공간, fixed size structured 변수 저장공간, 상수 저장공간이 여기에 포함된다.
2. Variable space requirements : 특정 요인(I)으로 size가 결정되는 structured variable, 재귀함수의 추가 공간 등이 여기 포함된다. 프로그램 P의 I에 대한 variable space requirement는 Sp(I)로 나타낸다.
전체 Space requirement는 S(P) = c + Sp(I)로 나타낸다.
(c는 당연히 fixed..)
space complexity를 분석할때 주로 Variable space requirement만 고려한다.
Example 1.6
float abc(float a, float b, float c) {
return a+b*c + 1.3;
}Fixed space requirements만 있으므로 Sabc(I) == 0이다.
Example 1.7
float sum(float list[], int n) {
float tempsum = 0;
int i;
for (i = 0; i < n; i++)
tempsum += list[i];
return tempsum;
}Pascal 같은 언어는 array를 다 받아오기 때문에 Ssum(I) == Ssum(n) == n이겠지만,
C는 주소만 받아오기때문에 Ssum(n) == 0이다.(즉, 모두 Fixed space requirements)
Example 1.8
float rsum(float list[], int n) {
if (n) return (rsum(list, n-1) + list[n-1]);
return 0;
}Example 1.7과 같은 함수지만 recursive version이다.
한번의 호출마다 2개의 parameter와 1개의 return address가 필요하다. sizeof operator로 byte 수를 구할 수 있다.
array pointer(list), integer(n)
, return address 모두 4bytes라고 가정하면,
Ssum(n) == 12*n이다.(1번 호출마다 12bytes)
n의 최댓값이 1000이라면, 총 12000bytes가 필요한 것이다.(n은 배열 크기랑 같음)
iteration 버전과 이렇게 공간 차이가 많이 난다.
1.5.2 Time Complexity
프로그램 p의 시간
compile time + run time(execution time) = T(p)
compile time은 fixed space requirements처럼 instance에 따라 변경되지 않는다. 특히, 한번 컴파일 시켜서 잘 돌아가게 했으면 recompile할 필요가 없이 그냥 실행할 수 있다.
따라서 우리는 run time(execution time)인 Tp에만 집중하면 된다.
Run time(Execution time)
Tp를 구하려면 compiler가 작동하는 방식, 즉 compiler가 source code를 object code로 변환하는 방식을 알아야하므로 쉽지 않은 작업이다.(예시 수식은 p.25)
그렇게 Tp(n)을 하나하나 다 계산하는건 노력에 비해 거의 의미가 없다.(running time을 측정하고자 한다면 최고의 방법은 그냥 system clock으로 재는 것이다.)
대신 우리는 program내의 operation의 숫자를 셀 수 있다.
그렇게 machine independent analysis를 할 수 있다. step을 나누는 기준은 아래와 같다.
Program step
DEFINITION
: A Program step is a syntactically or semantically meaningful program segment whose execution time is independent of the instance characteristics.
program step마다 계산한다, 즉, a=2나 a=b*7/3+4나 둘 다 one step이다.
one step은 instance characteristic과 독립돼야한다.
setp을 세기 위해 global variable을 만들어서 직접 count할 수 있다.
Example 1.9
executable statement에 대해서만 count를 하면 된다.
직접 count 변수를 넣어 count 해봄.
float sum(float list[], int n) {
float tempsum = 0; cout++; //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;
}다 축약해보면 2n+3이 된다.
Example 1.10
float rsum(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++; //for return
return 0;
}이런 함수의 경우 step count를 범위마다 확인해야한다.
n=0) if conditional과 두번째 return 실행 따라서 2
n>0) if conditional과 첫번째 return이 n번 실행, 그리고 마지막 호출에 +2가 된다. 따라서 2n+2
if문내에서 count 2증가 시켜야되지않나?
return문내의 함수 호출을 꺼내서 따로 쓰면 step 2개고, 같이쓰면 step 1갠가?
잘 이해는 안되지만 뭐 어떤 detail이 있지 않을까..
없더라도 애초에 그냥 간단하게 executable statement를 세는거니까 뭐..example 1.9의 iterative version보다 example 1.10의 step이 더 적다.
하지만 step수가 적다는게 꼭 시간이 적게 걸린단건 아니다. 각 step에 얼마의 시간이 걸릴지 모르기 때문이다.
위 경우도 보통 iterative 버전이 더 적은 시간이 걸린다.
Example 1.11
2차원 배열을 더하는 함수(p.28~29)의 step count를 해보면 2rows*cols + 2rows + 1이다.
즉, rows가 cols보다 꽤 크다면, 차라리 둘을 바꾸면 시간이 적게 걸린다.
1) 위에서처럼 count를 직접 넣어서 계산/실행시켜도되지만,
2) tabular method를 사용해도된다.
tabular method
우선 각 statement의 step count를 계산한다. 이를 step/execution(s/e)라고 한다.
그 다음 각 statement가 실행된 횟수인 frequency를 구한다. nonexecutable statement라면 frequency는 0이다.
그렇게 s/e와 frequency를 곱해서 나온 각 statement의 total step을 모두 더하면 된다.
ex)
| Statement | s/e | frequency | Total steps |
|---|---|---|---|
| float sum(float list[], int n) { | 0 | 0 | 0 |
| float tempsum = 0; | 1 | 1 | 1 |
| int i; | 0 | 0 | 0 |
| for (i = 0; i < n; i++) | 1 | n+1 | n+1 |
| tempsum += list[i]; | 1 | n | n |
| return tempsum; | 1 | 1 | 1 |
| } | 0 | 0 | 0 |
| 2n+3 |
Summary
time complexity는 number of step으로 표시된다.
number of steps은 instance characteristic의 함수이다. 필요한 part만 떼서 볼 수도 있다.
즉, number of input의 증가에 따른 run-time 증가를 보고싶으면, number of input만의 함수로 number of steps을 만들면 된다.
그래서 step count를 계산하기전에, instance의 어떤 characteristic을 사용할지 결정해야한다.
sum 함수에선 더해지는 element의 개수인 n의 함수로 측정하길 선택했고,
add 함수에선 더해지는 row의 개수와 column의 개수를 선택했다.
그렇게 relevant characteristic(n, m, p, q, r, ...)이 선택되면, step 정의할 수 있다.
step은 characteristic(n, m, p, q, r, ...)과 독립된 computation unit이다.
따라서 100번 더하거나 10번 곱하는건 1step이 될 수 있지만,
n번 더하거나 m/2번 빼거나 하는건 step으로 인정되지 않는다.
즉, statement 자체의 실행 시간이 problem size와 상관없다면 이는 1 step으로 인정되지만,
실행시간이 problem size에 좌지우지된다면 이는 step이 아니란 소리.
for(i=0;i<n;i++)도 보면 일단 얘 자체의 실행시간은 n과 상관없다.
frequency가 n이라서 step count가 n인거지, 저 statement는 1 step이 맞다.
하지만 n번 더하거나 n/2번 곱하는건 n이 어떤 숫자이냐에따라 해당 statement의 runtime이
달라지기때문에 그건 인정이 안된다고 바로 위 본문에서 얘기하고 있는 것이다.
(왜 인정안하지? n이 엄청 커지면 1step으로 보긴 어려워서 그런 것 같기도하고.. 자세힌모르겠네)
애초에 step을 세려면 instance characteristics와 independent여야하니 dependent인 예시는 없는건가위 예시들은 쉬웠지만, 그렇지 않은 경우도 많다.
binary search 함수(iteration ver.)만 봐도, element 개수인 n을 인자로 하려고하면 잘 안된다.(같은 n값이더라도 찾으려는 숫자의 위치에 따라 실행횟수가 달라진다.)
이런 경우 아래 3가지 종류의 step count를 정의하면 된다.
(1) best case : parameter에 대해 가장 적게 실행되는 case
(2) worst case : parameter에 대해 가장 많이 실행되는 case
(3) average : ~ 평균 실행 횟수
binary search 에서 element 개수 n으로 할때 평균 Time complexity 구하는 경우 : 링크
1.5.3 Asymptotic Notation(O, Ω, Θ)
step count를 하는 이유는 이를 다른 프로그램과 비교하고, instance characteristic이 변할때 run time의 변화를 보기 위해서이다.
step count(worst case, avrage 등등)를 정확하게 구하는 것은 꽤 어려운 작업이다.
게다가 어차피 step count 자체가 정확한 notation이 아니기 때문에 그걸 정확하게 구하려고 과하게 노력해봤자 크게 가치있진않다.
또 정확한 step count도 비교에 있어서 유용하진 않다.(어차피 비교니까..)
하지만, 100n+2나 2n+1처럼 step count 차이가 매우 큰 경우 이는 예외겠지만(이런 경우 전자의 runtime이 더 길다고 예측 할 수 있겠지), 굳이 저렇게 정확하게 안구하고 그냥 75n이나 80n정도까지만 알아도 같은 결과(전자의 runtime이 더 길다)를 얻을 수 있다.
프로그램 A의 time complexity가 an이고, 프로그램 B의 time complexity가 bn^2+cn이라면,
그래프에서 특정 수 k를 기준으로 교차하게되고, 둘의 runtime이 역전된다.
그 지점 k를 break even point라고 한다.
정확한 break even point는 분석해서 구할 순 없고 직접 돌려봐야된다.
Big-O (O) notation
DEFINITION
: f(n) = O(g(n)) iff(if and only if) there exist positive constants c and n0 such that f(n) <= cg(n) for all n (n >= n0)
: 쉽게 말해 asymptotic upper bound
Example 1.15
n>=2일때 3n+2 <= 4n 이므로, 3n+2 = O(n)이다.
n>=2일때 3n+2 <= 3n^2 이므로, 3n+2 = O(n^2)이다.(즉, g(n)이 upper bound이면 됨)
n>=5일때 10n^2+4n+2 <= 11n^2 이므로, 10n^2+4n+2 = O(n^2)이다.
10n^2+4n+2 =/= O(n)이다.
n>=4일때 6*2^n + n^2 <= 7*2^n이므로, 6*2^n + n^2 = O(2^n)이다.
O(1)은 computing time이 constant란 뜻이다.
O(n)은 linear, O(n^2)은 quadratic, O(n^3)은 cubic, O(2^n)은 exponential이라고 불린다.
ex. O(log n)이면 (n이 충분히 클때) O(n)보다 빠르다.
g(n)에 들어올 수식은 n>=n0인 경우 uppper bound이면 다 되지만(n = O(n) = O(n^2) = ...), 유용하게 사용하기 위해선 가장 작은 표현식이 와야한다.
물론 n = O(n^2)도 맞지만, 보통 그렇게 적진 않는다.
'f(n) = O(g(n))'은 맞지만 'O(g(n)) = f(n)'은 아니다. '=' 기호의 의미때문에 헷갈릴 수 있으니, 여기선 이를 'equal'이 아니라 'is'로 해석하자.
Theorem 1.2
: If f(n) = a_k*n^k + ... + a_1*n + a_0 (다항식꼴), then f(n) = O(n^m)
Proof
시그마 사용해서 위 식 정리한 후, 크거나 같은 식으로 변형하여 "n^m * 상수" 꼴로 나타내서 증명했다.
Omega (Ω) notation
DEFINITION
: f(n) = Ω(g(n)) iff there exist positive constants c and n0 such that cg(n) <= f(n) for all n (n >= n0)
: 쉽게 말해 asymptotic lower bound
Example 1.16
n>=1일때 3n <= 3n+2 이므로, 3n+2 = Ω(n)이다.
n>=1일때 1 <= 3n+2 이므로, 3n+2 = Ω(1)이다.(즉, g(n)이 lower bound이면 됨)
n>=1일때 n^2 <= 10n^2+4n+2 이므로, 10n^2+4n+2 = Ω(n^2)이다.
10n^2+4n+2 =/= Ω(n^3)이다.
n>=1일때 2^n <= 6*2^n + n^2이므로, 6*2^n + n^2 = Ω(2^n)이다.
또한 6*2^n + n^2 = Ω(n^100)이다.
또 6*2^n + n^2 = Ω(1)이다.
첫번째 경우는 0 이상이라고 해도 되지만 오메가 정의에 따르면 n0는 양수라서 1로 했다.얘도 마찬가지로 가장 큰 표현식으로 보통 표현한다.
Theorem 1.3
: If f(n) = a_k*n^k + ... + a_1*n + a_0 (다항식꼴)이고 a_m > 0 이면, then f(n) = Ω(n^m)
Theta (Θ) notation
DEFINITION
: f(n) = Θ(g(n)) iff there exist positive constants c1, c2 and n0 such that c1*g(n) <= f(n) <= c2*g(n) for all n (n >= n0)
Example 1.17
n>=2일때 3n <= 3n+2 <= 4n 이므로, 3n+2 = Θ(n)이다. c1은 3이고, c2는 4.
10n^2+4n+2 = Θ(n^2)이다.
10n^2+4n+2 =/= Θ(n)이다.
10n^2+4n+2 =/= Θ(n^4)이다.
big-O나 omega notation보단 정확하다.
lower이며 upper bound이다.
g(n)을 나타낼때 대부분 coefficient(계수)를 작성하지 않는데, 이는 관습이다. O(3n) -> 이런식으로 적어도 틀린건 아니지만 이렇게 적진 않는다.
Theorm 1.4
: If f(n) = a_k*n^k + ... + a_1*n + a_0 (다항식꼴)이고 a_m > 0 이면, then f(n) = Θ(n^m)
Example 1.18
step count에서처럼 tabular 방식을 사용할 수 있다.
asymtotic notation을 사용하는게, step count보다 더 간단하게 나타낼 수 있어서 편리하다.
Example 1.19
binary search의 time complexity 여기에 자세한 내용
Example 1.20
permutation 함수의 asymtotic notation을 구해보자.
i=n) Θ(n) 이다.
i<n) else clause로 들어가서, 그 안의 for loop가 n-i+1"번" 돌아간다.
그리고 각 loop는 1번 도는데 Θ(n+Tperm(i+1,n)) 만큼의 시간이 걸린다. (안에 recursive 고려해야되고, 마지막엔 i=n 이므로 n이 걸려서 +n을 해줬다.)
(i<n인 조건은 처음에 i<n이란거지 iteration 진행되면서 결국 i는 n이 된다.)
즉, (i<n)인 경우 Tperm(i,n) = Θ((n-i+1)(n+Tperm(i+1,n)))
위에서 말했듯이, i+1<=n이면 Tperm(i,n) = Θ((n-i+1)(Tperm(i+1,n))) (마지막괄호에 n을 더할 필요가없다.. i가 n인 경우는 고려안하니까)
이걸 이용해 풀어내면
Tperm(1,n) = Θ(n(n!)) 이다. (n>=1)
Example 1.21
magic square(마방진)은 자연수 n에 대해 n^2 이하의 숫자로 n×n matrix를 채운다. 각 열과 행의 덧셈결과는 같아야하며, 가장 긴 대각선 길이도 같아야한다.
n이 홀수일때 coxeter가 magic square를 만드는 방법을 제안했는데,
일단 제일 위 row의 가운데에 1을 적는다. 나머지 부분은 좌상단으로 갈수록 숫자가 증가하게 작성하는데, 범위를 넘어서면 반대편의 대응되는 위치에 이어적는다.(해당 마방진 복사본들이 사방으로 붙어있다고 생각하고 좌상단으로갈수록 숫자를 하나씩 늘려서 적는다. 물론 이렇게적으면 다시 순환되는 부분은 증가하지 않을수도있다. 예시는 책 참고)
프로그램 만든거 책 보고 하나하나 for문이나 statement 분석해봐도 제일 큰게 Θ(n^2)이다.
따라서 해당 프로그램의 asymtotic complexity는 Θ(n^2)이다.
ㅡㅡ
앞으로의 분석에선 주로 big-O notation을 사용할 것이다. 그게 널리 쓰이기때문(current trend).. theta도 뭐 분석해서 써도 됨.
1.5.4 Practical complexities
Program P의 asymtotic complexity가 Θ(n)이고, Program Q의 asymtotic complexity가 Θ(n^2)이라면 충분히 큰 n일때 우리는 P가 더 빠르다고 할 수 있다.(break even point)
여기서 이 "충분히 큰 n"을 그냥 무시해선 안된다.
만약 우리가 사용하려는 n 충분히 큰 경우가 아니라면 P가 Q보다 빠르다고 할 수 없다. 심지어 그런 경우에서 프로그램을 사용한다면 우린 program P를 사용해야 할 것이다.
두 프로그램이 각각 n*10^6과 n^2의 complexity를 가진다면 n이 10^6보다 작은 범위에서 사용할때는 후자 프로그램을 이용하는게 맞다.책에 나오는 여러 식의 n값에 따른 변화도 어느정도 공부해둘 필요가 있다.
2^n이 가장 가파르게 증가하고, logn이 가장 원만하게 증가한다. 작은 범위에선 또 각각 따져봐야한다.
2^n step을 가지는 프로그램에 대해, 컴퓨터가 1초에 1 billion(십억) step을 계산할 수 있다고 가정)
n=40일 경우, 18.3분 필요
n=50일 경우, 13일 필요
n=60일 경우, 310.56년 필요
이런 경우 보통 n<=40 인 경우에서만 사용한다.
n^10 step을 가지는 프로그램에 대해, 컴퓨터가 1초에 1 billion(십억) step을 계산할 수 있다고 가정)
(이런꼴도 지수가 크면 꽤 오래걸린다. == 사용이 제한된다.)
n=10일 경우, 10초 필요
n=100일 경우, 3171년 필요
실용적인 측면에서 결국 n이 꽤 크다면(n>100) n, logn, n^2, n^3 같은 작은 complexity를 가진 애들만 가능하다.
(이 책을 쓴 시점에 가장 빠른 컴퓨터가 1초에 1billion instruction 수행한다고했음)
(해당 컴퓨터 기준으로 시간 계산한건 p.44 표에 정리돼있다.)
1.6 PERFORMANCE MEASUREMENT
1.6.1 Clocking
analysis도 좋지만, 특정 machine에서 직접 측정을 해야 할때도 있다.
C는 clock이나 time 함수를 이용해 실제 시간을 측정할 수 있다.
(해당 함수 사용법은 생략하겠음, knk나 이 책 봐도 되고 여기봐도 되고,, DS책에선 time_t 값 뺄때 difftime 함수 쓰라고함)
Example 1.22
책에 실제로 selection sort의 시간을 측정하는 코드가 있다.
(reverse order array를 사용해서 worst case 측정)
보면 시간이 제대로 측정되지 않을 수도 있는데, 방법은 맞지만 너무 짧아서 애초에 제대로 측정되지 않는 것이다.
그래서 이 책에선 충분한 시간을 얻을때까지 반복하도록, program 1.24를 보완해 program 1.25를 만들었다.(1.25에만 array initialize가 포함된 부분에 대해선 크게 상관없지만, 정~확한 결과를 얻고싶으면 저 부분만 따로 측정하고 결과에서 빼도 된다.)
1.62 Generating Test Data
test data를 얻는건 생각보다 쉽지않다. 어떤 경우는 특정 프로그램을 사용해야 할 수도 있다.
우린 위에서 worst case를 여러번 돌려서 구했지만, average case를 구하는 것은 더 어렵다.
모든 경우를 다 계산해서 평균을 내기엔, sort 프로그램의 경우 n!개를 모두 테스트해봐야하므로 쉽지않은 작업이다.
worst case이든 average case이든 모든 case를 다 시도할 순 없다.
따라서 데이터를 잘 추출하기위해 해당 algorithm을 분석해야한다.
(이는 algorithm specific task라 여기서 안다룬다고함)
1.7 SELECTED READING AND REFERENCES
C와 asymtotic analysis 책 추천 목록
나중에 볼 일 생기면 한번 보지뭐
