2023-01-11T07:30:29.723Z

0

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

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

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

0

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

0

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

0

확인했습니다. ㅎㅎ 함수호출이 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도 생각하실 부분이 있는것이죠.

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

감사합니다.

0

감사합니다!