다항식 선형 시간에 계산하기

$f(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$이라는 다항식이 있을 때, 이 값은 선형 시간에 계산할 수 있다.

간단한 변환을 거치면 쉽게 알아차릴 수 있는데,

$f(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_n + 0)))$으로 변환 가능하기 때문이다.

코드는 다음과 같다.

길이 n+1의 배열은 $a_0,\;a_1,\;a_2,...,a_n$이 저장되어있는 배열이라고 하자

int poly(int x, int* arr, int n) { // n은 배열의 길이 (최고차항+1)
	int r = 0;
	for (int i = n; i > 0; --i) {
		r += arr[i];
		r *= x;
	}
	r += arr[0];
	return r;
}