Bài toán Min_Max

Tìm giá trị Min, Max của đoạn a[l..r] của mảng a[1..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;

}

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

T ( n / 2 ) + T ( n / 2 ) + 2 ; n > 2 1 ; n = 2 0 ; n = 1 T ( n ) = { { size 12{T ( n ) =alignl { stack { left lbrace T ( n/2 ) +T ( n/2 ) +2;n>2 {} # right none left lbrace 1;n=2 {} # right none left lbrace 0;n=1 {} # right no } } lbrace } {}

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

T(n) = 2 + 2T(n/2) = 2 + 2² + 2² T(n/2²) = 2^k-1T(2) + ∑i=1k−12i size 12{ Sum cSub { size 8{i=1} } cSup { size 8{k - 1} } { { size 24{2} } rSup { size 8{i} } } } {}

= ∑i=1k2i−2k−1=2k+1−2k−1−2=3n2−2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{k} } { { size 24{2} } rSup { size 8{i} } } - { size 24{2} } rSup { size 8{k - 1} } = { size 24{2} } rSup { size 8{k+1} } - { size 24{2} } rSup { size 8{k - 1} } - 2= { {3n} over {2} } - 2} {}

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