인프런 커뮤니티 질문&답변

함수 호출횟수 ^ n이라고 뭔가 딱 생각하고 말기에는 그러면 이전에강의에나왔던

int sum = go + go 이부분에서도 함수호출이 2번이니까 2^n이어야 되는게 아닌가요?

go에 들어가는 인자의 값이 반씩 줄어서 다르게 생각해야한다라고하기엔 피보나치도 뭔가 인자로 들어가는 값이 하나씩 줄고있는데 둘이 시간복잡도가 갈리는 이유가뭔가용?

음.. 이전강의 어떤 부분 말씀하시는 거죠? 해당 강의 제목 말씀 부탁드립니다.

시간복잡도 Q3 문제에 go함수가 나옵니다!

확인했습니다. ㅎㅎ 함수호출이 2번이면 보통은 2 ^ n이 나옵니다.

Q3 같은 경우 그런 걸 아는 사람들을 위해 꼰 문제라고 보시면 되는데요. 저 문제는 해당 범위는 딱 한번만 출력이 됩니다. 즉, 중복되는 범위가 없습니다. 그렇기 때문에 함수 호출이 많이 줄어든 것입니다.

좀 더 자세히 얘기해볼까요?

저 문제의 함수를 보면

자, n이 16일 때

1, 2, 4, 8, 16 이런식으로 호출이 되죠?

1, 2, 4, 8을 모두 더하면? 15가 됩니다. 그렇기 때문에 2 *n >> O(n)의 시간복잡도를 가집니다.

#include<bits/stdc++.h>
using namespace std;  
int n, a[1004], cnt;
int go(int l, int r){ 
	cout << l << " : " << r << '\n';
	cnt++;
	if(l == r) return a[l];  
	int mid = (l + r) / 2; 
	int sum = go(l, mid) + go(mid + 1, r); 
	return sum;
}
int main(){
	cin >> n; 
	for(int i = 1; i <= n; i++){
		a[i - 1] = i; 
	}
	int sum = go(0, n - 1);
	cout << sum << '\n';  
	cout << cnt << '\n';  
} 

근데 피보나치는 왜 그게 안되냐면. 일단 go(n - 1)부터 시작해서.... go(1)까지 호출이 되죠? n번

go(n - 2) 또한 .....go(1)까지 호출이 되죠? n번, 범위도 중복이 되기 때문에 더 많이 호출이 됩니다. go하나당 이런게 2번씩.. 2번씩 되면서 그 해당 함수는 n번... 그래서 2 ^ n이 됩니다.

보통의 재귀함수는 go(n - 1) 또는 go(idx + 1) 이라는 구조를 가지기 때문에 보통은 2 ^ n이라고 보시면 되지만 Q3도 생각하실 부분이 있는것이죠.

또한 해당 부분은 강의 설명에 보완설명 넣어 놓겠습니다.

감사합니다.

감사합니다!