페르마 판정법 썸네일형 리스트형 거듭제곱, 최대공약수, 소수판정 최적화 (+ 확률에 의한 판정) 특정 산술 계산들에 적용할 수 있는 최적화 아이디어를 살펴보자. 거듭제곱 bⁿ 을 구하는 재귀함수는 다음과 같이 작성할 수 있다. function exp(b, n){ return n === 0 ? 1 : b * exp(b, n - 1); } 이 때의 증가차수는 O(n)이 될 것이다. 여기서 다음 연속제곱식을 이용하면 증가차수를 O(logn)으로 줄일 수 있다. bⁿ = (b½ⁿ)² : n = 짝수 bⁿ = b * bⁿ⁻¹ : n = 홀수 코드로 나타내면 다음과 같다. function exp(b, n){ return n === 0 ? 1 : n % 2 === 0 ? exp(b, n / 2) ** 2 : b * exp(b, n - 1); } exp(b, n / 2) 으로 치환할 때마다 필요한 단계수가 절반으.. 더보기 이전 1 다음