글 읽기 - 이러한 코드를 짰을 때 시간복잡도가 어떻게 될까요?

onsbtyd 2년 전 0

백트래킹을 이용하여 조합을 선택해 O(k)인 임의의 코드를 시행하는 코드입니다.

그런데 이코드의 시간복잡도가 궁금하여 for문이 도는 횟수를 단순카운트 했더니 조합의 경우의 수와 어느정도 비슷하지만 조금 많게 나왔습니다.

n!보다는 작고 조합의 경우의 수보단 많을 것 같은데 이 코드의 시간복잡도가 어떻게 될까요?

int n;//n개 중
int m;//m개 선택
int check[20];//조합 저장
void back(int loc, int now) {
	if (now == m + 1) {
		//시간복잡도 k인 임의의 코드
	}
	else {
		for (int i = loc + 1; i <= n; i++) {
			check[now] = i;
			back(i,now+1);
		}
	}
}

int main(){
    back(0,1);
}

jinhan814 2년 전 2

적당한 상한과 하한은 쉽게 보일 수 있습니다. 하한은 6번 줄의 실행 횟수가 nCm이니 nCm입니다. 상한은 6번 줄에서 완성되는 수열이 nCm개이고, 수열의 길이는 m개이니 check[now] = i 대입이 많아야 m * nCm번 일어나서 m * nCm입니다.

또는 back(loc, now) 함수가 실행되면 길이가 now - 1이고, 마지막 수가 loc로 끝나는 수열이 구해져있는 상태이고, 같은 수열은 두 번 이상 호출되지 않으니 길이가 1 <= i <= m인 수열의 개수를 세면 됩니다. back(0, 1)은 for문이 아니라 다른 곳에서 호출되니 i = 0인 경우는 빼줘야 합니다. 따라서 실제 실행 횟수는 nC1 + ... + nCm입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이러한 코드를 짰을 때 시간복잡도가 어떻게 될까요?

onsbtyd 2년 전 0

jinhan814 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말