인프런 커뮤니티 질문&답변
작성한 질문수
문제로 해결하는 시간복잡도 4번 질문이 있습니다.
작성
·
112
0
우선, 1. cnt를 찍으며 여러가지 케이스를 도출한 다음 -> 2. (시간이 있다면) 점화식 만들고 / 일반적으로는 어림 잡아서 -> 3. 규칙을 찾아 식으로 만든 후 빅 오 표기법으로 표시한다이런 식으로 복잡도를 구하면 될까요?? 그리고 해당 문제에 대해서는요,저같은 아주 초보자가 복잡도가 Log 랑 관련있겠다 는 걸 아예 감도 못잡고 예제를 통해 규칙을 찾아내고자 3, 6, 15 등...2의 제곱이 아닌 수를 입력하는 경우가 있을 수도 있잖아요. 그럼 더 헷갈릴 것 같은데, 선생님께서는 애초에 2의 제곱을 cin으로 입력 하시면서 규칙을 찾아내시더라구요. 혹시 2의 제곱 수들을 넣어서 예시 값 들을 도출해 내신 이유가 /2 때문인가요?? /= 2 로 나오는 것들의 예시 값들을 도출해 낼 때는 log를 염두 해 두면 될까요??
답변 1
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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.