SICP JS - 1.2: 함수와 함수가 생성하는 프로세스

SICP JS를 읽고, 이미 체득했다고 생각하는 정보들은 제외한 후 기억해둘 만하다 생각한 정보를 나열(정리가 아니다!)하였다.

동일한 입력에 대해 동일한 출력을 가지는 함수라고 해도, 그 ‘형태’에 따라서 서로 다른 특징을 따름.

프로세스가 실행됨에 따라, ‘지연된 연산의 연쇄’(a chain of deferred operations)를 만들어가며 확장된 것을 실제로 계산해나가며 축소하는 형태 → ‘재귀적 프로세스’(recursive process)

• 지연된 연산의 연쇄 길이, 즉 결과를 얻기 위해 추적해야 하는 정보량이 입력의 크기에 선형적으로 비례할 때, 이를 **선형 재귀적 프로세스(linear recursive process)**라고 함
• 결과를 얻기 위해 추적해야 하는 정보가 트리 형태를 이룰 때, 이를 **트리 재귀적 프로세스(tree-recursive process)**라고 하며, 이 때 실행될 단계의 개수는 입력의 크기에 지수적으로 비례하며 필요한 공간은 트리의 높이에 선형적으로 비례함

고정된 개수의 상태 변수, 프로세스가 실행됨에 따라 각 상태 변수를 어떻게 갱신할 지에 대한 규칙과 종료 조건을 통해 표현되는 형태 → ‘반복적 프로세스’(iterative process)

• 결과를 얻기 위해 실행될 단계의 개수가 입력의 크기에 선형적으로 비례할 때, 이를 **선형 반복적 프로세스(linear iterative process)**라고 함

반복적 프로세스의 경우, 임의 시점에 대한 프로세스의 상태는 상태 변수를 통해 완전하게 표현될 수 있다. 특정 시점에 계산을 멈췄다가 재개하기 위해서는 상태 변수를 제공하기만 하면 된다.

재귀적 프로세스의 경우, 프로세스를 실행하고 있는 주체가 ‘지연된 연산의 연쇄’ 중 어디가 실행되고 있는지에 대한 ‘숨겨진’(코드 상에 드러나지 않는) 정보를 추가적으로 관리한다.

’재귀적 프로세스’와 ‘재귀 함수’를 혼동하지 않도록 주의!

a의 n제곱($a^n$)을 계산할 때, b가 큰 수인 경우 연속제곱법을 이용하여 실행될 단계 개수와 필요한 공간의 크기를 n의 로그 함수($log(n)$)에 비례하게 줄일 수 있다.

두 정수 a와 b(a ≥ b), 그리고 a를 b로 나눈 나머지 r에 대해, a와 b의 최대공약수는 b와 r의 최대공약수와 서로 같으며 이를 이용하여 큰 수의 최대공약수를 효율적으로 구하는 방법을 유클리드 호제법이라고 한다. 이를 위해 필요한 단계의 개수는 $log(a)$와 $log(b)$에 비례한다.

n이 소수가 아니라면 $\sqrt{n}$보다 작거나 같은 약수를 가지고 있어야 하며, 이러한 사실을 통해 n이 소수임을 판별하기 위해서 필요한 단계의 개수는 $\sqrt{n}$에 비례한다.

n이 소수이고 a가 n보다 작은 양의 정수라면 $a^n≡a\mod{n}$이며(페르마의 소정리), 이 정리를 이용하여 소수 여부를 판별하기 위해 필요한 단계의 개수는 경우 $log(n)$에 비례한다. 그러나 이 알고리즘은 모든 경우에 대해 올바르지 않으며, 해당 판별법을 거쳤음에도 n이 소수가 아닐 가능성이 존재한다. 이러한 형태의 알고리즘을 ‘확률적 알고리즘’(probabilistic algorithm)이라고 한다.