Please purchase a
Please purchase a
personal license.
personal license.
B
B
À
À
I TO
I TO
Á
Á
N ĐA TH
N ĐA TH
Ứ
Ứ
C
C
B
B
à
à
i to
i to
á
á
n đa th
n đa th
ứ
ứ
c

Thu
Thu
ậ
ậ
t to
t to
á
á
n cơ b
n cơ b
ả
ả
n
n
 Thuật toán:
result = a
0
+ a
1
*x;
xpower = x;
for (int i=2;i<n;i++)
{ xpower = xpower *x;
result = result + a
i
*xpower;
}
Đánh giá thuật toán:
- Số phép cộng: 1+ (n-1) = n
- Số phép nhân: 1+ 2*(n-1) = 2n-1

0
 ({…[(a
n
x+a
n-1
)*x+a
n-2
]*x+…+a
2
}*x+a
1
)*x+a
0
Thuật toán:
result = a
n
;
for (int i=n-1;i>=0;i )
{ result = result * x;
result = result + a
i
;
}
Thu
Thu
ậ
ậ
t to
t to
á

ố
ố
Ví dụ: Tính x
256
C1: for (int i=1;i<=256;i++)
result = result * x;
 Thực hiện 255 phép nhân
C2: result = x*x;
result = result * result; // 3 times
 Thực hiện 4 phép nhân
Thu
Thu
ậ
ậ
t to
t to
á
á
n ti
n ti
ề
ề
n x
n x
ử
ử
lý h
lý h
ệ
ệ

n x
ử
ử
lý h
lý h
ệ
ệ
s
s
ố
ố
Đánh giá thuật toán:
P(x)=(x
4
+5)*[(x
2
-1)*(x+4)+(x+12)]+[(x
2
+1)*(x-11)+(x-26)]
- Số phép nhân: x
2
 1 phép nhân
x
4
= x
2
*x
2
 1 phép nhân
 3 phép nhân

Cơ bản 2n-1 n
Horner n n
Xử lý hệ số n/2+lgn (3n-1)/2