Thuật toán chia để trị (Divide and Conquer) là một phương pháp giải quyết bài toán bằng cách chia nhỏ bài toán thành nhiều bài toán con nhỏ hơn, sau đó giải quyết từng bài toán con và kết hợp kết quả để giải bài toán lớn ban đầu. Đây là một kỹ thuật thường được áp dụng cho các bài toán có thể được phân tách thành các bài toán nhỏ có cấu trúc tương tự bài toán ban đầu.
Một thuật toán chia để trị thường có 3 bước chính:
Dưới đây là một số ví dụ điển hình về cách áp dụng thuật toán chia để trị trong PHP.
QuickSort là một trong những thuật toán sắp xếp nổi tiếng sử dụng kỹ thuật chia để trị. Ý tưởng của QuickSort là chọn một phần tử làm pivot (phần tử trụ), sau đó chia mảng thành hai phần: một phần chứa các phần tử nhỏ hơn pivot, và một phần chứa các phần tử lớn hơn pivot. Sau đó, áp dụng đệ quy để sắp xếp từng phần nhỏ.
function quickSort(array $arr): array {
if (count($arr) < 2) {
return $arr; // Mảng có 1 hoặc 0 phần tử thì không cần sắp xếp
}
// Chọn phần tử pivot (phần tử đầu tiên)
$pivot = $arr[0];
// Chia mảng thành hai phần dựa trên pivot
$left = [];
$right = [];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] <= $pivot) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
// Đệ quy sắp xếp từng phần, sau đó kết hợp lại
return array_merge(quickSort($left), [$pivot], quickSort($right));
}
// Ví dụ sử dụng
$arr = [3, 6, 8, 10, 1, 2, 1];
$sortedArr = quickSort($arr);
print_r($sortedArr);
MergeSort là một thuật toán sắp xếp khác sử dụng phương pháp chia để trị. Thuật toán này chia mảng thành hai nửa bằng nhau, sau đó sắp xếp từng nửa bằng cách tiếp tục chia và sắp xếp, cuối cùng kết hợp hai mảng đã sắp xếp để tạo thành mảng hoàn chỉnh.
function mergeSort(array $arr): array {
if (count($arr) <= 1) {
return $arr; // Mảng có 1 hoặc 0 phần tử thì không cần sắp xếp
}
// Chia đôi mảng
$mid = (int)(count($arr) / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
// Đệ quy sắp xếp từng phần
$left = mergeSort($left);
$right = mergeSort($right);
// Kết hợp hai mảng đã sắp xếp
return merge($left, $right);
}
function merge(array $left, array $right): array {
$result = [];
$i = 0;
$j = 0;
// Kết hợp hai mảng đã sắp xếp
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$result[] = $left[$i];
$i++;
} else {
$result[] = $right[$j];
$j++;
}
}
// Thêm các phần tử còn lại
return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}
// Ví dụ sử dụng
$arr = [3, 6, 8, 10, 1, 2, 1];
$sortedArr = mergeSort($arr);
print_r($sortedArr);
Thuật toán Binary Search cũng là một ví dụ điển hình của chia để trị. Binary Search tìm kiếm một phần tử trong mảng đã sắp xếp bằng cách chia mảng làm đôi, so sánh phần tử cần tìm với phần tử ở giữa và tiếp tục tìm trong nửa mảng thích hợp.
function binarySearch(array $arr, int $target, int $left, int $right): int {
if ($left > $right) {
return -1; // Phần tử không tồn tại
}
$mid = (int)(($left + $right) / 2);
if ($arr[$mid] === $target) {
return $mid; // Tìm thấy phần tử
} elseif ($arr[$mid] > $target) {
return binarySearch($arr, $target, $left, $mid - 1); // Tìm trong nửa bên trái
} else {
return binarySearch($arr, $target, $mid + 1, $right); // Tìm trong nửa bên phải
}
}
// Ví dụ sử dụng
$arr = [1, 2, 3, 6, 8, 10];
$target = 6;
$index = binarySearch($arr, $target, 0, count($arr) - 1);
echo $index;
Thuật toán chia để trị là một trong những phương pháp tối ưu hóa quan trọng giúp giải quyết bài toán lớn bằng cách chia nhỏ chúng thành các bài toán con. Các thuật toán sắp xếp như QuickSort và MergeSort hay thuật toán Binary Search là những ví dụ tiêu biểu. Áp dụng thuật toán này giúp cải thiện hiệu suất cho các bài toán lớn và phức tạp.
Trong PHP, bạn có thể dễ dàng áp dụng các thuật toán chia để trị để giải quyết các vấn đề liên quan đến sắp xếp, tìm kiếm hoặc các bài toán tương tự.
