자료구조론(2)

---

함수 호출

int main(void)
{
	int sum;
    int a=4. b=5;
    sum = add(a,b);
    cout << sum;
    return 0;
}
   
int add(int a, int b)
{
	int c;
    c = a+b;
    c = substract(c,9);
    return c;
}

int substract(int a, int b)
{
	int c;
    c = a+b;
    return c;
}

위코드를 이미지화하면 다음과 같다.

---

재귀 함수

함수는 함수 구현에서 자기 자신의 함수를 호출 가능하다.

자기 자신 함수의 호출을 재귀 호출이라 하고 이러한 특징을 재귀라 한다.

 

팩토리얼 함수를 예시로 들면 다음과 같다.

int main(void) 
{
	int num = 3, val;
	val = fact(num);
	cout << "fact = “ << val;
	return 0; 
}

int fact( int n) 
{
	if(n==0)
		return 1;
	else
		return fact(n-1)*n; 
}

---

복잡도 분석

복잡도는 다양한 방식으로 분석이 되지만 그중 Big O notation에 대해 알아봤다.

우선 복잡도(complexity)는 시간복잡도(time complexity)와 공간복잡도(space complexity)로 나눠진다.

Big O notation은 그중 시간복잡도 분석방식이다. Big O notation은 7개의 카테고리로 나눠진다.

7Categories: O(2^n), O(n^2), O(nlogn), O(n), O(logn), O(loglogn), O(1)

뒤로 갈 수록 복잡도가 낮은 좋은 알고리즘이라고 볼 수 있다.

1.

int main(void)
{
	int num = 3, val;
	val = fact(num);
	cout << “fact = “ << val;
	return 0;
}

int fact( int n)
{
	if(n==0)
		return 1;
	else
		return fact(n-1)*n;
}

2.

int main(void)
{
	int i,n=1;
	for(i=1;i<=3;i++)
		n *= i;
	cout << “fact = “ << val;
	return 0;
}

두가지 방식으로 팩토리얼을 코딩하고 복잡도 분석을 진행하니 다음과 같다.

---