Kỹ năng tối ưu hoá thuật toán
Nguyễn Duy Hàm
Tối ưu hoá là một đòi hỏi thường xuyên không chỉ trong quá trình giải quyết các bài toán
tin học, mà ngay trong giải quyết các công việc thường ngày của chúng ta. Tối ưu hoá
thuật toán là một công việc yêu cầu tư duy thuật toán rất cao, cùng với khẳ năng sử dụng
thuần thục các cấu trúc dữ liệu. Lần này tôi xin được chia sẻ với các bạn về tối ưu hoá
thuật toán trong giải quyết một bài toán tưởng chừng rất đơn giản, nhưng việc tìm ra thuật
toán tối ưu cho nó lại không dễ chút nào. Tối ưu hoá thường được tiến hành theo 2 góc độ
đó là tối ưu theo không gian có nghĩa là tối ưu không gian lưu trữ (bộ nhớ), và tối ưu theo
thời gian có nghĩa là giảm độ phức tạp thuật toán, giảm các bước xử lý trong chương
trình…Tuy nhiên không phải lúc nào ta cũng có thể đạt được đồng thời cả 2 điều đó, trong
nhiều trường hợp tối ưu về thời gian sẽ làm tăng không gian lưu trữ, và ngược lại.
Phát biểu bài toán
Cho dãy số a
0
, a
1
, …, a
n-1
(0 < n < 10.000), hãy tìm dãy con có tổng lớn nhất của dãy số đó.
Yêu cầu đưa ra tổng lớn nhất và chỉ sổ đầu và cuối của dãy con tìm được. Hạn chế của bài
toán là thời gian chạy 0.005s trên máy P4 2.4Ghz.
Chúng ta thấy rằng bài toán khá đơn giản, song nếu không được giải quyết tốt sẽ không
đáp ứng được yêu cầu về thời gian. Với các bài toán có hạn chế về thời gian như thế, đòi
hỏi ta phải đưa ra được thuật toán tối ưu nhất.
Cách giải thứ nhất:
Cách làm sơ khai nhất là xét tất cả các đoạn con có thể theo đoạn mã sau:
int Findmax(int a[],int &dau,int &cuoi){
max=a[0];dau=cuoi=0;
for(i=0;i<N;I++){< p>
for(j=i;j<N;J++){< p>

cuoi=j;
dau=i;
}
}
return max;
}
Thuật toán trên sử dụng 2 vòng lặp lồng nhau, vòng đầu tiên lặp n lần, vòng thứ 2 lặp tối
đa n lần, nên dễ thấy độ phức tạp của thuật toán này là O(n
2
). Tôi tin rằng nhiều người sẽ
đồng ý sử dụng cách làm trên, nhưng chắc chắn 1 điều là nó không đáp ứng được đòi hỏi
về thời gian, không tin các bạn cứ thử xem!
Cách giải thứ 3:
Ta cùng tìm hiểu một cải tiến khác chắc chắn sẽ tốt hơn. Ta sử dụng thêm 2 mảng k,c mỗi
mảng gồm n phần tử. Trong đó k[i] sẽ lưu giá trị lớn nhất của tổng dãy con mà a[i] là cuối
dãy, c[i] sẽ lưu chỉ số đầu của dãy đó. Như vậy k[i]=max(a[i],a[i]+k[i-1]). Hãy theo dõi
đoạn mã khá lí thú sau, nó được xây dựng trên tư tưởng quy hoạch động trên:
int Findmax(int a[],int &dau,int &cuoi){
k[0]=max=a[0];c[0]=dau=cuoi=0;
for(i=1;i<N;I++){< p>
s=k[i-1]+a[i];
k[i]=a[i];
c[i]=i;
if (s>k[i]){
k[i]=s;
c[i]=c[i-1];//đầu dãy
}
//tìm tổng lớn nhất
if (k[i]>max){
max=k[i];

cuoi=i;//cuối dãy
luu=dau;//đầu dãy
}
}
dau=luu;
return max;
}
Cách làm trên quả thật rất hiệu quả, tuy nhiên nó đã làm biến đổi dãy số ban đầu(mảng a).
Làm sao có thể giữ nguyên dãy số, không dùng thêm mảng phụ, vẫn đáp ứng được yêu cầu
đề bài. Với một cải tiến nhỏ ta sẽ thấy ở đoạn mã sau thật tuyệt vời:
int Findmax(int a[],int &dau,int &cuoi){
dau=luu=cuoi=0;max=s=a[0];
for(i=1;i<N;I++){< p>
s+=a[i];
if (s<A[I]){< p>
s=a[i];
dau=i;
}
//tìm tổng lớn nhất
if (s>max){
max=s;
cuoi=i;//cuối dãy
luu=dau;//đầu dãy