Tối ưu hóa thuật toán
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (88.17 KB, 6 trang )
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>
s=0;
for(k=i;k<=j;k++)
s+=a[k];
if (max<S){< p>
max=s;
dau=i;
cuoi=j;
}
}
}
return max;
}
Ta dễ thấy rằng cách làm trên có độ phức tạp O(n
3
) với 3 vòng for lồng nhau. Đoạn mã trên
có quá nhiều cái để ta có thể tối ưu, ví dụ như khi tính tổng từ i->j đã không tận dụng được
tổng từ i->(j-1) đã được tính trước đó! Do vậy đây là 1 đoạn mã khó có thể chấp nhận được
về mặt kĩ thuật lập trình lẫn kĩ năng viết chương trình.
Cách làm thứ 2:
Với 1 cải tiến nhỏ ta sẽ xét hết tất cả các dãy con có thể của dãy số bắt đầu từ vị trí thứ i
(i=0,1,2…n-1), với việc tận dụng lại các giá trị đã được tính trước đó. Chúng ta cùng theo
dõi đoạn mã sau:
int Findmax(int a[],int max,int &dau,int &cuoi){
max=a[0];dau=cuoi=0;
for(i=0;i<N-1;I++){< p>
s=0;
for(j=i;j<N;J++){< p>
s+=j;
if (s>max){
max=s;
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
}
}
dau=c[cuoi];
return max;
}
Với thuật toán trên độ phức tạp là O(n) với chỉ 1 vòng lặp n lần duy nhất. Như vậy, có thể
nói ta đã tối ưu xong về mặt thời gian từ độ phức tạp O(n
3
) xuống còn O(n). Về không gian
bộ nhớ, ở cách làm trên ta đã sử dụng thêm 2 mảng k và c mỗi mảng n phần tử, nếu không
gian đầu vào không phải hạn chế 10.000 mà là 20.000 thậm chí 30.000 thì sao? Chắc chắn
sẽ không đủ không gian bộ nhớ để sử dụng 2 mảng k và c như trên. Vậy giải quyết thế
nào? Ta sẽ dễ dàng bỏ mảng k đi khi sử dụng tính toán hoàn toàn trên mảng a, vậy có thể
bỏ nốt mảng c đi không? nếu bỏ đi thì ta sẽ xác định giá trị đầu của mỗi dãy như thế nào?
Cách thứ 4:
Tại mỗi vị trí đang xét ta sẽ so sánh để tìm ra dãy có tổng lớn nhất ngay như trên, và như
vậy ta sẽ sử dụng 1 biến để lưu giá trị đầu của dãy tìm được! Ý tưởng đó thể hiện qua đoạn
mã sau:
int Findmax(int a[],int &dau,int &cuoi){
dau=cuoi=luu=0;max=a[0];
for(i=1;i<N;I++){< p>
a[i]+=a[i-1];
if (a[i]<A[I]-A[I-1]){< p>
a[i]-=a[i-1];
dau=i;
}
//tìm tổng lớn nhất
if (a[i]>max){
max=a[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
