Bài toán

Tìm giá trị Min, Max của đoạn a[l..r] của mảng a[1..n]

Phân tích thuật toán

Tại mỗi bước, chia đôi đoạn cần tìm rồi tìm Min, Max của từng đoạn, sau đó tổng hợp lại kết quả . Nếu đoạn chia chỉ có 1 phần tử thì Min = Max và bằng phần tử đó

Minh họa :

Tìm giá trị Min, Max trong đoạn a[2..7] của mảng a[1..7] .

Ký hiệu :

MinMax(a,l,r,Min,Max) cho Min và Max trong đoạn a[l..r]

MinMax(a,2,7,Min,Max) cho Min =0 và Max=15 trong đoạn a[2..7]

Mô tả thuật toán:

Input : a[l..r], ( l ≤ r )

Output: Min = Min (a[l],..,a[r]),

Max = Max (a[l],..,a[r]).

MinMax(a,l, r, Min, Max)

if (l == r)

{

Min = a[l];

Max = a[l];

}

Else

{

MinMax(a,l, (l+r) / 2, Min1, Max1);

MinMax(a,(l+r) /2 + 1, r , Min2, Max2);

If (Min1 < Min2)

Min = Min1;

Else

Min = Min2;

If (Max1 > Max2)

Max = Max1;

Else

Max = Max2;

}

Độ phức tạp thuật toán

Gọi T(n) là số phép toán so sánh cần thực hiện. Khi đó ta có:

$\begin{array}{}T(n/2)+T(n/2)+2;n>2\\ 1;n=2\\ 0;n=1\\ \\ T(n)=\begin{array}{}\{\{\end{array}\\ \end{array}$

Với n=2^k , thì:

T(n) = 2 + 2T(n/2) = 2 + 2² + 2² T(n/2²) = 2^k-1T(2) + $\sum _{i=1}^{k-1}{2}^i$

= $\sum _{i=1}^k{2}^i-2^{k-1}=2^{k+1}-2^{k-1}-2=\frac{\mathrm{3n}}{2}-2$

Vậy T(n) € O(n).