Kĩ thuật lập trình - Chương 3: Kỹ thuật tối ưu hóa chương trình

Chương 3:Kỹ thuật tối ưu hóa chương trìnhTrịnh Huy HoàngKhoa Công nghệ thông tinĐại học Sư phạm TPHCMNội dungCác mức thiết kế một chương trìnhCác kỹ thuật tối ưu hóa chương trìnhKỹ thuật tinh chế mãKỹ thuật tối ưu hóa rẽ nhánhKỹ thuật tối ưu hóa các vòng lặpTối ưu hóa chương trình bằng bảng truy cậpTối ưu bằng cách giảm thiểu gọi chương trình conCác mức thiết kế một chương trìnhĐặc tả bài toánThiết kế cấu trúc hệ thốngCấu trúc dữ liệu và thuật toánTinh chế mã (tối ưu hóa chương trình)Tính độ phức tạp của thuật toánLư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ể.Ví dụ 1: Viết chương trình tính tổng S=1+x/1!+x2/2!++xn/n!s=1;for(i=1;ia[j]) {t=a[i];a[i]=a[j];a[j]=t;} j=j+1; } i=i+1;} i=1;while(ia[j]) {t=a[i];a[i]=a[j];a[j]=t;} if((j+1a[j+1])) {t=a[i];a[i]=a[j+1];a[j+1]=t;} j=j+2; } i=i+1; }Tối ưu hóa chương trình bằng bảng truy cậpNếu viết các hệ số trong khai triển nhị thức Newton ta có thể thiết kế đoạn chương trình sau:Int ckn(int k,int n){ if((k==0)||(k==n)) return 1; else return ckn(k,n-1)+ckn(k-1,n-1);}Cải tiếnfor(i=1;i<=n;i++) {c[i][1]=1;c[i][i]=1;}for(i=2;i<=n;i++) { ii=i/2+1; for(j=2;j<=ii;j++) {c[i][j]=c[i-1][j]+c[i-1][j-1]; c[i][i-j+1]=c[i][j]; } }Tối ưu bằng cách giảm thiểu gọi chương trình conSo sánh 2 chương trình và cho lời nhận xétVí dụ: tính (sinx+cosx)+ (sin2x+cos2x)++ (sinnx+cosnx)float tinh(int i) { return sin(i*x)+cos(i*x);}void main(){ s=0; scanf(“%d”,&x); x=x*3.14/180; for(i=1;i<=100;i++) s=s+tinh(i); printf(“%f”,s);}float tinh(int n){ float t; int i; s=0; for(i=1;i<=n;i++) {t=i*x; s=s+sin(t)+cos(t);} return s;}void main(){ scanf(“%d”,&x); x=x*3.14/180; s=tinh(100); printf(“%f”,s);}