Inflearn Community Q&A
asked
1-N 코드 질문있습니다
Resolved
Written on
·
365
0
안녕하십니까 큰돌님
강의 보기 전에 문제를 풀어봤는데 틀렸다고 나와서 질문드립니다. 최대 범위인 20억 * 20억일 때 long long 범위가 넘는데 pow 반환값을 long long 에 저장해서 틀린게 맞을까요 ?? 그리고 pow함수의 시간복잡도는 어떻게 되는지도 궁금합니다
Answer 3
1
이거 알림이 대댓으로 달면 안떠서 이렇게 답변 드려용.
밑은
log2입니다.
반으로 쪼개지는 걸 생각하시면 됩니다.
답변 수정드릴게 있는데요.
로직 자체는
20억의 20억승이나
pow함수 자체가 log이기 때문에
대기업님이 구축하신 코드의 시간복잡도는 log20억이라고 보시면 됩니다.
1
그리고 pow에 대해 조금 더 자세히 설명드리자면 pow는 다음과 같이 설계되어있습니다.
그렇기 때문에 logb의 시간복잡도를 갖게 됩니다.
int power(int x, unsigned int y)
{
int temp;
if (y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return temp * temp;
else
return x * temp * temp;
}
log의 밑은 크게 중요하지 않은 건가요 ??
예를 들어서 pow(a, b)일 때 log_a(b) 이렇게까지 생각할 필요는 없는 건가요 ??
1
안녕하세요 대기업님 ㅎㅎ 반갑습니다.
최대 범위인 20억 * 20억일 때 long long 범위가 넘는데 pow 반환값을 long long 에 저장해서 틀린게 맞을까요 ??
>> 네 맞습니다. 근데 조금은 틀려요.
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
자 그러면 20억 * 20억이 아니라 20억의 20억승이 들어갈 수도 있겠죠?
그래서 범위를 초과합니다.
pow함수의 시간복잡도는 어떻게 되는지도 궁금합니다
>> pow(a, b)라고 했을 때 O(logb)가 됩니다.
감사합니다.
친절한 답변 감사합니다 !!
계속 열심히 해보겠습니다 !!