-o0--Lại bàn về chia để trị--0o-

[Orient]

THUẬT TOÁN CHIA ĐỂ TRỊ
-----------------------
Thuật toán chia bài toán gốc thành nhiều bài toán con nhỏ hơn, với mỗi bài toán con lại tiếp tục chia thành các bài toán nhỏ hơn nữa. Cho đến khi các bài toán con có kích thước đủ nhỏ có được lời giải, kết thúc việc chia. Tổng hợp lại chúng thì có được lời giải cho một số bài toán gốc.
-----------------------
Tìm kiếm nhị phân đơn giản dùng mảng

Tìm kiếm một giá trị x trong một mảng a đã được sắp xếp tăng dần:

BS(int x,int a[n])
{
if (n==1)
if(x==a[n]) return 1;
else return 0;
else
{
k=n/2;
if(x==a[k]) return 1;
else if(x<a[k]) return BS(x,a[1..k-1]);
else return BS(x,a[k+1..n]);
}
}
------------------------
Độ phức tạp
Gọi T(n) là độ phức tạp của thuật toán, ta có Hệ thức truy hồi:
T(n)=T(n/2)+1, T(1)=1;
Giả sử n=2mk // kí hiệu của 'n=2 mũ k'
T(n)=T(n/2)+1
=(T(n/2m2)+1)+1=T(n/2m2)+2
=...
=T(n/2mk)+k
Theo cách đặt ta có(n=2mk,T(1)=1):
T(n)=1+k, mà k=lgn
=>T(n)=lgn+1
Vậy T(n)=O(lgn).
--------------------------
Trích "Phan Thanh Tao"

[mabun]

Ai có bài về so sánh giữa 2 thuật toán chia để trị và quy hoạch động không cho mình với. Thanks!

[bld]

chia để trị là đi từ trên xuống , chia ra chia ra chia ra , rồi lại đi từ dưới lên
QHD là giải hết mấy ông lẻ tẻ , rồi hợp lại hợp lại hợp lại , cho đến khi được ong lớn nhất , tóm lại là đi từ dưới lên