우리가 프로그램을 판단하는 데에는 다음과 같은 몇 가지 기준을 바탕으로 한다.
1. 프로그램이 원래의 명세와 부합하는가?
2. 정확하게 작동하는가?
3. 프로그램을 어떻게 사용하고, 또 어떻게 수행하는지에 관한 문서(메뉴얼)화가 프로그램 되어 있는가?
4. 프로그램에서 논리적인 단위를 생성하기 위해 함수를 효과적으로 사용하는가?
5. 프로그램의 코드의 가독성이 좋은가?
6. 프로그램이 주기억장치화 보조기억장치를 효율적으로 사용하는가?
7. 작업에 대한 프로그램의 실행 시간은 받아들일 만한가?
프로그램의 공간 복잡도
프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양 ( 메모리 / 주기억 장치를 어느정도 사용하는가? )
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구
S(P) = c + Sр(I)
고정 공간 : 코드 저장 공간 / 단순 변수 / 고정 크기의 구조 변수 / 상수
가변 공간 : 추가로(동적으로) 필요로 하는 공간들 ( 고정이 아님 )
인스턴스 I (기능) 에 작업을 하는 프로그램 P의 가변 공간 요구는 Sр(I)로 표기한다.
예1)
이 함수는 오직 고정 공간 요구만을 가지고 있으므로 Sabc(I) = 0
float abc(float a,float b,float c)
{
return a+b+b*c+(a+b+c) / (a + b) + 4.00;
}
예2) 입력이 n개의 요소를 갖는 배열이라면 n은 인스턴스 특성이 된다.
만약,Sp(I) 를 계산할 때 n이 유일한 인스턴스 특성이라면 우리는 Sp(I)를 표현하기 위해서 Sp(n)을 사용할 것이다.
call by value n을 배열의 크리로 한다면 : Ssum(I) = Ssum(n) = n
call by address : Ssum(n) = 0
float sum(float list[], int n)
{
....
}
예3)
n이 MAX SIZE 라면 : Srsum(n) = 6*n / 12*n / 48*n
float rsum(float list[] , int n)
{
if(n) return rsum (list, n-1) + list[n-1];
return 0;
}
|
데이터 타입 |
이름 |
바이트수 |
|
매개변수 : 부동소수 매개변수 : 정수 복귀 주소 : 내부적으로 사용 |
list[] n
|
2(4)(16) 2(4)(16) 2(4)(16) |
|
순환 호출당 총 합계 |
|
6(12)(48) |
프로그램의 시간 복잡도
프로그램을 실행시켜 완료하는 데 필요한 컴퓨터 시간의 양을 의미한다.
프로그램 실행시간 Tp를 결정하는 것은 컴파일러의 속성에 대한 상당한 지식이 요구되기 때문에 쉬운 작업이 아니다.
즉, 컴파일러가 어떻게 원시 프로그램을 목적 코드로 변환시키는지 알아야 한다.
예를 들어 수치값을 더하고 빼는 간단한 프로그램을 가정해 보자.
n이 인스턴스 특성을 나타낸다고 가정하면,Tp(n)은 다음과 같이 표현할 수 있다.
Tp(n) = CaADD(n) + CsSUB(n) + CiLDA(n) + CstSTA(n)
여기서 Ca,Cs,Ci,Cst 는 각각의 연산을 수행하기 위해 필요한 시간을 나타내는 상수이다.
ADD,SUB,LDA,STA는 인스턴스 특성n으로 프로그램을 수행하기 위해 덧셈,뺄셈적재,저장 연산이
실행되는 횟수이다.
실행 시간에 대한 자세한 견적을 얻기 위해서 노력할 필요는 없다.
만약 실행 시간을 꼭 알아야 한다면, 가장 좋은 방법은 시스템 클럭을 이용해서 시간을 재는 것이다.
다른 방법은 프로그램이 수행하는 연산의 횟수를 계산하는 것이다.
이것은 컴퓨터에 독립적인 견적이 된다. 그러나 프로그램을 어떻게 상이한 단계로 분할할 것인가를 알아야 한다.
( 프로그램 단계(스텝) : 구문적으로나 의미적으로 뜻을 갖는 프로그램 세그먼트 )
유의할 것은 프로그램 세그먼트(스텝)에 의해 표현되는 계산양은 다른 세그먼트에 의해 표현되는 계산의 양과
다르다는 것이다. 예를 들어, a=2와 같이 간단한 배정문(대입문?)을 한단계로 간주할 수 있고,
a = 2*b + 3*c/d-e+f/g/a/b/c 같이 더 복잡한 연산문을 역시 한 단계로 간주할 수도 있다.
우리가 필요한 요건은 한 단계로 간주되는 각 명령문을 실행하는 데 필요한 시간이 인스턴스 특성에 독립적이어야
한다는 것이다. ( 전제 조건 단계는 특성에 독립적일것 / 동일하게 취급할것? )
.단계수 구해보기 예)
float sum(float list[],int n)
{
float tempsum = 0; <- 배정문 연산
int i;
for(i=0 ; i < n ; i++)
{ <- 루프연산
tempsum += list[i]; <- 배정문 연산
}
<- 마지막 루프연산
<- 반환문 연산
}
즉 다은과 같이 나타낼 수 있다.
float sum(float list[],int n)
{
count+=1;
for(i=0 ; i < n ; i++)
{
count+=2;
}
count+=2;
}
즉 count의 최종값은 2n + 3 이 된다.
만약 위의 코드를 순환함수(재귀)로 변경한다면 실제 반복 함수보다 순환함수의 단계수가 더 작다는 것을 알 수있다.
float rsum(float list[],int n)
{
count++; -> if 연산
if(n)
{
count++; -> rsum 재 호출
}
count++; -> return
}
즉 count의 최종값은 2n + 2가 된다.
n == 0 : 2
n > 0 : 2n
이 단계수는 우리에게 얼마나 많은 단계가 수행되는지를 말해줄 뿐이지, 각 단계가 얼마나 많은 시간이 걸리는지를
말해주는 것이 아니라는 것을 기억해야 한다. 그래서 비록 순환함수가 단계는 적지만 통상적으로 반복 함수보다
실행 속도가 더 느리다. 왜냐하면 순환 함수의 단계가 반복 함수의 단게보다 평균 더 많은 시간이 걸리기때문이다.
단계수는 테이블 방식으로 나타낼 수 있다.
|
문장 |
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 0 1 0 1 0 0 0 |
0 0 0 rows + 1 0 rows * (cols + 1) 0 rows * cols 0 0 0 |
0 0 0 rows + 1 0 rows*cols + rows 0 rows*cols 0 0 0 |
|
합계 |
2(rows*cols) + 2rows + 1 | ||
테이블로 표현하는게 훨씬 보기 쉬운것 같다.
역시 문서 정리의 기본은 ㅡㅡ 테이부울?? ㅎㅎ
상수는 생략하고 최고차항만 생각함으로 2(rows*cols) + 2rows + 1 를 빅-오 표기법으로 표시하면
O(rows*cols) 이고 rows 와 cols 를 같은 n으로 놓고 보면 O(n^2)이 된다.
알고리즘 복잡도의 함수값은 아래 사이트를 참고
http://blog.naver.com/loudon23
참고 :
정렬에서 시간 복잡도 계산을 하는데 퀵 정렬의 경우 최악이 n^2 이고 평균이 nlogn 이다.
하지만 정렬에서 퀵.히프 등등.. 정렬을 사용해야할 경우를 한번 고려해 보자.
만약 1 부터 10까지의 숫자를 정렬해야 한다면? O(n) 으로도 끝낼수 있다는점!!