본문 바로가기

제곱근 시간 복잡도

(1)

[Java] 모듈러 제곱근 모듈러 제곱근이란?거듭제곱근(P^N)을 효과적으로 계산하기 위한 방식 거듭제곱근을 구하기 위해서 단순 루프를 돌면서 곱셈을 하였을 때, 그 횟수가 늘어날수록 극격히 비효율적이 된다. 단순 루프for(int i = 0; i 위와 같은 방식으로 P^N을 구하면 O(N)의 시간복잡도를 갖는다. 모듈러 제곱근 예시 코드public static long power(long P, long N) { long result = 1; while(N > 0) { if(N % 2 == 1) { result *= P; } P *= P; N /= 2; } return result;}모듈러 제곱근을 이용하면 O(logN)의 시간 복잡도로 ..

이전 1 다음

728x90

티스토리툴바