인프런 커뮤니티 질문&답변

이거 알림이 대댓으로 달면 안떠서 이렇게 답변 드려용.

밑은

log2입니다.

반으로 쪼개지는 걸 생각하시면 됩니다.

답변 수정드릴게 있는데요.

로직 자체는

20억의 20억승이나

pow함수 자체가 log이기 때문에

대기업님이 구축하신 코드의 시간복잡도는 log20억이라고 보시면 됩니다.

그리고 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;
}

안녕하세요 대기업님 ㅎㅎ 반갑습니다.

최대 범위인 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)가 됩니다.

감사합니다.