Chương 3:
Kỹ thuật tối ưu hóa chương trình
Trịnh Huy Hoàng
Khoa Công nghệ thông tin
Đại học Sư phạm TPHCM
Nội dung
Các mức thiết kế một chương trình
Các kỹ thuật tối ưu hóa chương trình
–Kỹ thuật tinh chế mã
–Kỹ thuật tối ưu hóa rẽ nhánh
–Kỹ thuật tối ưu hóa các vòng lặp
–Tối ưu hóa chương trình bằng bảng truy cập
–Tối ưu bằng cách giảm thiểu gọi chương trình con
Các mức thiết kế một chương trình
1. Đặc tả bài toán
2. Thiết kế cấu trúc hệ thống
3. Cấu trúc dữ liệu và thuật toán
4. Tinh chế mã (tối ưu hóa chương trình)
5. Tính độ phức tạp của thuật toán
Lưu ý
Trước khi viết chương trình:
+ Không nên mã hóa 1 chương trình ngay khi chỉ
mới có ý tưởng đầu tiên mà phải xem xét tất cả
các mức thiết kế có thể để chọn ra 1 thiết kế làm
tăng tốc nhanh nhất với phí tổn ít nhất.
+ Nên thử nhiều mức thiết kế khác nhau bằng
cách giải quyết bài toán trên nhiều mặt từ đó
chọn được 1 thiết kế tối ưu về không gian và thời
gian.
Kỹ thuật tinh chế mã
Ta có thể tối ưu chương trình về mặt thời
gian hoặc không gian (rất khó thực hiện
được cả hai), nếu muốn tối ưu cả hai khía
cạnh trên thì ta phải thay đổi thuật toán. Ở
chương này ta xét các kỹ thuật tối ưu
chương trình về mặt cấu trúc, tìm 1 thuật giải
có độ phức tạp tốt nhất có thể.