거듭제곱 문제를 생각해보자. 밑 b와 0보다 큰 지수 n을 받아 b^n 을 구하는 프로시저로 나타낼 수 있다.
재귀 프로세스
(define (expt b n)
(if (= n 0)
b
(* b (expt b (- n 1)))))위 프로시저는 n이 증가함에 따라 계산도 선형 비례하여 증가하며(O(n)), 앞 수가 몇번 나왔는지 기억해야 하므로 저장 공간도 선형 비례하여 증가한다.(O(n))
반복 프로세스
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b (- counter 1) (* b product))))위 프로시저는 n이 증가함에 따라 계산도 선형 비례하여 증가하지만(O(n)), 인자로 현재까지의 상태를 넘겨주므로 저장 공간을 추가로 사용하지 않는다.(O(1))
분할 정복 프로세스
(define (fast-expt b n)
(cond ((= n 0) 1)
((is-even n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))위 프로시저는 b^n 을 구할 때, b^n = b^(n/2) * b^(n/2) 임을 이용하여 빠르게 계산한 프로세스이다.
n이 증가함에 따라 계산은 log2 n 에 비례하여 증가하며, 저장 공간 역시 마찬가지다.(O(logN))
두 수의 최대 공약수를 구하는 알고리즘을 알아보자.
유클리드 알고리즘
a, b 두 수가 있을 때 (a >= b) a를 b로 나눈 나머지를 r이라 하면, GCD(a, b) = GCD(b, r) 이다.
r이 0이 될때까지 연산을 반복하면, 첫번째 인자가 최대 공약수가 된다.
이를 프로시저로 나타내보자.
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))위 프로시저는 계산 단계가 로그에 비례하는데, 이에 대해 알아보자.
라메의 정리
유클리드의 알고리즘으로 GCD를 구하는 데 k 단계를 거치는 경우, 두 수 가운데 작은 수는 k번째 피보나치 수보다 크거나 같아야 한다. (귀납법으로 증명 가능)
유클리드 알고리즘의 시간복잡도
유클리드 알고리즘에서 두 수중 작은 수를 n이라 하고, k단계를 거쳐 계산했다고 하자.
라메의 정리에 의해 n >= Fib(k) 이고, 앞서 Fib(k) 는 ϕ^k/sqrt(5) 와 가까운 정수임을 밝혔으므로, k 는 ϕ를 밑으로하는 n의 로그에 비례한다. (식 양쪽에 ϕ를 밑으로하는 로그를 씌우면 k 와 logϕ(N) 이 비례함)
소수를 찾는 프로세스를 살펴보자.
n이 소수가 아니라면, sqrt(n) 보다 작거나 같은 약수가 무조건 존재한다. (d 가 n의 약수이면, n/d도 n의 약수이므로)
따라서 1부터 sqrt(n) 까지 n의 약수가 존재하는지 알아보는 방법으로 n이 소수인지 판단할 수 있다. (O(sqrt(N)))
페르마의 작은 정리: n이 소수고, a가 n보다는 작고 0보다는 큰 정수라면, a^n과 a는 modulo n 으로 맞아 떨어진다. (a^n 과 a 는 n에 대해 합동이다.)
페르마 검사
임의의 a<n을 만족하는 a 를 골라 a^n modulo n 을 계산하여 나머지를 얻는다.
나머지가 a 라면 n은 소수일 확률이 높고, 나머지가 a가 아니라면 n은 소수가 아니다.
페르마 검사를 특정 횟수 이상 통과하면 소수일 확률이 매우 높고, 통과하지 못하면 소수가 아니다.
확률을 바탕으로 하는 알고리즘
일반적인 알고리즘은 정확한 답을 낸다. 하지만, 위 페르마 검사를 반복하는 것은 정확한 답이라고 보기 어렵다.
n이 소수가 아닌데도 페르마 검사를 통과하는 a가 존재하기 때문이다. (이 수를 카마이클 수라 한다.)
페르마 검사를 보완하여 틀리지 않도록 검사하는 밀러-라빈 검사도 존재한다.
페르마 검사는 암호화 알고리즘인 RSA 알고리즘에서도 사용되며 확률 알고리즘도 유용할 수 있다는 큰 사례가 되었다.