-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
1-N 코드 질문있습니다
23.07.12 19:19 작성 조회수 246
0
안녕하십니까 큰돌님
강의 보기 전에 문제를 풀어봤는데 틀렸다고 나와서 질문드립니다. 최대 범위인 20억 * 20억일 때 long long 범위가 넘는데 pow 반환값을 long long 에 저장해서 틀린게 맞을까요 ?? 그리고 pow함수의 시간복잡도는 어떻게 되는지도 궁금합니다
답변을 작성해보세요.
1
큰돌
지식공유자2023.07.13
그리고 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;
}
1
큰돌
지식공유자2023.07.13
안녕하세요 대기업님 ㅎㅎ 반갑습니다.
최대 범위인 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)가 됩니다.
감사합니다.
답변 3