C++ 반복함수와 재귀함수의 시간복잡도 비교하기 - 대학교 컴공 2학년 자료구조 과목

배열요소의 합을 구하는 반복함수

//배열의 합을 구하는 함수
#include<iostream>
using namespace std;
float Sum(float* a, const int n) {
	float s = 0.0;
	for (int i = 0; i < n; i++) s = s + a[i];
	return s;
}

int main() {
	float arr[] = { 1,3,4,5 };
	int size = 4;
	cout<<Sum(arr, size);
}

float Sum(float* a, const int n) 함수의 구조를 팍팍 파악해보자. 실수형 자료형 float인 함수 Sum()은 매개변수로 float*a와 const int n을 가지고있다. main함수에서는 실수형 배열요소를 가진 배열과 배열요소의 갯수 n이 지역변수로 존재한다.

함수의 구조로 들어가보면, 실수 s를 0.0으로 초기화한 후에 i가 0부터 n-1일 때까지 s+=a[i];를 실행한다. 
그러고, s를 반환하는 함수이다.

그래서 그냥 배열의 요소를 차례 차례 s에 더해 13을 반환한다.

배열요소의 합을 구하는 재귀함수

//배열의 합을 구하는 재귀함수
#include<iostream>
using namespace std;

float Rsum(float* a, const int n) {
	if (n <= 0) return 0.0;
	else return (a[0] + Rsum(&a[1], n - 1));
}

int main() {
	float arr[] = { 1,3,4,5 };
	int size = 4;

	cout<<Rsum(arr, size);

}

위 함수는 재귀함수이다. n이 0보다 작거나 같을 때 0.0을 반환한다. 하지만 n이 0보다 클 때는 a[0] + Rsum(&a[1], n-1) 을 반환한다. 잘 이해가 안되니 main함수로 가보자.

1+Rsum(arr[1]인 3의 메모리주소,3)를 반환한다.
음.. Rsum(&a[1],n-1) 하면, 그냥 크기가 n-1이고 배열의 시작의 주솟값이 기존 배열의 a[1]의 주솟값인 새로운 배열로 탄생하나보다. 이해했다.와 이거 이해하는데 진짜 오래걸렸다. 하지만 자학은 하지말자. 그럴시간이 없다ㅠㅠ 

암튼 맨 처음에
1. 1+Rsum(&arr[1],3)를 반환한다.
2. 1+ 3+Rsum(새로운 배열의&arr[1],2)을 반환한다.
3. 1+3+ 4+Rsum(새로운 배열의 &arr[1],1)을 반환한다.
4. 1+3+4+5+Rsum(새로운 배열의 &arr[1],0)을 반환한다.
5. 1+3+4+5+0 을 반환한다.
그래서 13이 나온다.

시간복잡도 비교하기

아!!!! 드디어 함수를 풀긴 풀었으니 원래 목적이었던 시간복잡도를 비교해보자. 이 시간복잡도 비교하는게 사실상 내 자료구조 시험의 첫번째 범위인건데 난 지금 시험이 23.10.26인데 시험 나흘 전에 이제 이걸 나가고있다. 올리는 건 아마 예약발행으로 27일날 올라갈듯. 그 땐 시험도 본 후겠지.. 그래도 지금이라도 나가는게 어디냐. 화이팅!!!! 시작해보자

1. 반복문에서 float s= 0.0;, int i=0;, return s; 와 같이 1회 초기화하거나 반환하는 식은 상수로 따진다. 따라서 3.
for(int i=0; i<n;i++) s=s+a[i]; 에서 초기화하는 int i=0;을 제외하고 i<n; ,i++ , s =, s+, a[i]총 5개 항은 n회 반복한다. 따라서 5n+3
2. 재귀함수에서 1회 반환하는 return 0.0; 을 상수로 따져 상수 1, 
if(n<=0) , return (a[0]+Rsum(&a[1], n-1)); 은 n번 반복되는 항의 갯수가 6개이므로 6n+1