문제로 해결하는 시간복잡도 4번 질문이 있습니다.

작성한 질문수 9

0

안녕하세요 룰루님ㅎㅎ

1. cnt를 찍으며 여러가지 케이스를 도출한 다음 -> 2. (시간이 있다면) 점화식 만들고 / 일반적으로는 어림 잡아서 -> 3. 규칙을 찾아 식으로 만든 후 빅 오 표기법으로 표시한다

>> 네 맞습니다. 이렇게 하시면 됩니다.

선생님께서는 애초에 2의 제곱을 cin으로 입력 하시면서 규칙을 찾아내시더라구요. 혹시 2의 제곱 수들을 넣어서 예시 값 들을 도출해 내신 이유가 /2 때문인가요??
>> 음... 편의상 그렇게 한 것이구요. 2의 제곱수를 입력으로 넣지 않아도 밑이 2인 logN의 시간복잡도를 가집니다.

/= 2 로 나오는 것들의 예시 값들을 도출해 낼 때는 log를 염두 해 두면 될까요??

>> 음.. 무조건 /=2가 있다? = log 이게 아니라

이런식으로 다른 중요한 로직은 없고

N자체를 계속해서 /= 2를 해나아간다 = 밑이2인 logN 시간복잡도를 가진다.

라고 생각하시면 될 것 같습니다.

void solve(int N){
	int a = 0, i = N;
	while (i > 0) {
		a += i;
		i /= 4;
	} 
	cout << a << '\n';
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.