DAA - Vấn đề Max-Min

Chúng ta hãy xem xét một vấn đề đơn giản có thể được giải quyết bằng kỹ thuật chia và chinh phục.

Báo cáo vấn đề

Bài toán Max-Min trong phân tích thuật toán là tìm giá trị lớn nhất và nhỏ nhất trong một mảng.

Giải pháp

Để tìm số lớn nhất và số nhỏ nhất trong một mảng nhất định numbers[] có kích thước n, thuật toán sau có thể được sử dụng. Đầu tiên, chúng tôi đại diện chonaive method và sau đó chúng tôi sẽ trình bày divide and conquer approach.

Phương pháp ngây thơ

Phương pháp ngây thơ là một phương pháp cơ bản để giải quyết bất kỳ vấn đề nào. Trong phương pháp này, số tối đa và số tối thiểu có thể được tìm thấy riêng biệt. Để tìm số lớn nhất và số nhỏ nhất, có thể sử dụng thuật toán đơn giản sau.

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

Phân tích

Số lượng so sánh trong phương pháp Naive là 2n - 2.

Có thể giảm số lượng so sánh bằng cách sử dụng phương pháp chia và chinh phục. Sau đây là kỹ thuật.

Cách tiếp cận Phân chia và Chinh phục

Theo cách tiếp cận này, mảng được chia thành hai nửa. Sau đó, sử dụng phương pháp đệ quy số tối đa và tối thiểu trong mỗi nửa được tìm thấy. Sau đó, trả về giá trị lớn nhất của hai cực đại của mỗi nửa và giá trị nhỏ nhất của hai cực tiểu của mỗi nửa.

Trong bài toán đã cho này, số phần tử trong một mảng là $ y - x + 1 $, trong đó y là lớn hơn hoặc bằng x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ sẽ trả về giá trị lớn nhất và nhỏ nhất của một mảng $ \ mathbf {\ mathit {number [x ... y]}} $.

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

Phân tích

Để cho T(n) là số phép so sánh được thực hiện bởi $ \ mathbf {\ mathit {Max - Min (x, y)}} $, trong đó số phần tử $ n = y - x + 1 $.

Nếu T(n) đại diện cho các số, sau đó quan hệ lặp lại có thể được biểu diễn dưới dạng

$$ T (n) = \ begin {case} T \ left (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} \ rceil \ right ) +2 & cho \: n> 2 \\ 1 & cho \: n = 2 \\ 0 & cho \: n = 1 \ end {case} $$

Hãy để chúng tôi giả định rằng n ở dạng quyền lực của 2. Vì thế,n = 2^k Ở đâu k là chiều cao của cây đệ quy.

Vì thế,

$$ T (n) = 2.T (\ frac {n} {2}) + 2 = 2. \ left (\ begin {array} {c} 2.T (\ frac {n} {4}) + 2 \ end {array} \ right) + 2 ..... = \ frac {3n} {2} - 2 $$

So với phương pháp Naïve, trong cách tiếp cận chia để trị, số lượng phép so sánh ít hơn. Tuy nhiên, bằng cách sử dụng ký hiệu tiệm cận, cả hai cách tiếp cận đều được biểu diễn bằngO(n).