문제로 해결하는 시간복잡도 4번 질문이 있습니다.
177
작성한 질문수 9
우선, 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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
코딩 살구 클럽 로그인 문제
0
33
2
2-J 채점관련 질문
0
31
3
코딩 살구 클럽 Python 지원 가능 여부
0
50
1
살구클럽 아이디 없음 문제
0
58
1
1-O 코딩살구클럽 채점관련 질문
0
46
2
히든 테스트 케이스가 사라졌습니다
0
42
1
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
57
2
살구 클럽 채점 관련 문의(테스트 케이스)
0
52
2
1-H 문제 채점하기 오류
0
47
3
코딩살구클럽 2주차 2-L 문제 채점하기 오류
0
43
2
살구 클럽 채점 관련 문의
0
55
2
코딩 살구 클럽 실전 세션
0
48
2
코딩살구클럽 채점 관련 질문
0
43
2
코딩살구클럽 컴파일에러
0
74
2
5-B
0
48
2
4 - A
0
53
2
코딩살구클럽 입장이 안됩니다
0
124
2
4-F 경우의 수 질문입니다.
0
53
2
코딩살구클럽 가입이 안됩니다.
0
121
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
78
1
교안 158페이지 문의드립니다
0
54
2
코딩살구클럽 관련 건의사항
0
162
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
54
1
진행 방법 질문드립니다!
0
102
2