3.3 Thuật toán heap sort
4. Các bài toán chia để trị
4.1 Tìm tập con liên tục có tổng lớn nhất
https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1
Cho một mảng gồm N số nguyên. Tìm mảng con liền nhau có tổng lớn nhất.
Bài toán dùng brute-fore ta có độ phức tạp sẽ là O(n^3), bằng cách xét tổng của tất cả các mảng con liền nhau:
int maxSubarraySum(int arr[], int n){
int maxsum = arr[0];
for (int i = 0; i < n; i ++) {
for (int j = i; j < n; j ++) {
int sum = 0;
for (int k =i; k <= j; k++) sum+= arr[k];
if (sum > maxsum)
maxsum = sum;
}
}
return maxsum;
}
Áp dụng chia để trị ta có thể giải bài toán này theo cách sau:
Chia mảng ban đầu thành hai mảng
Trả ra tổng lớn nhất của:
Tổng lớn nhất của mảng bên trái (bằng cách gọi đệ quy)
Tổng lớn nhất của mảng bên phải (bằng cách gọi đệ quy)
Tổng lớn nhất của mảng gồm phần tử cả phần tử ở giữa
int maxCrossingSum(int arr[], int l, int m, int h)
{
int sum = 0;
int left_sum = INT_MIN;
for (int i = m; i >= l; i--) {
sum = sum + arr[i];
if (sum > left_sum) {
left_sum = sum;
}
}
sum = 0;
int right_sum = INT_MIN;
for (int i = m + 1; i <= h; i++) {
sum = sum + arr[i];
if (sum > right_sum) {
right_sum = sum;
}
}
return max(left_sum + right_sum, left_sum, right_sum);
}
int maxSubArraySum(int arr[], int l, int h)
{
if (l == h)
return arr[l];
int m = (l + h) / 2;
return max(maxSubArraySum(arr, l, m),
maxSubArraySum(arr, m + 1, h),
maxCrossingSum(arr, l, m, h));
}
4.2 Tìm cặp điểm gần nhất
https://www.spoj.com/problems/CLOPPAIR/
Cho N điểm trên một mặt phẳng và nhiệm vụ của bạn là tìm một cặp điểm có khoảng cách giữa chúng là nhỏ nhất. Tất cả các điểm sẽ là duy nhất và chỉ có một cặp có khoảng cách nhỏ nhất.
Áp dụng brute-fore: bằng cách tìm khoảng cách của tất cả các cặp điểm để tìm ra đáp án. Độ phức tạp sẽ là O(n^2).
struct Point
{
int x, y;
};
float bruteForce(Point P[], int n) {
float min = FLT_MAX;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
double dist(Point p1, Point p2) {
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
Áp dụng chia để trị, chúng ta có thể giải bài toán này như sau:
Sắp xếp tất cả các điểm theo tọa độ X
Chia các điểm ra làm hai phần
Đệ quy để tìm khoảng cách nhỏ nhất của hai dãy d1 và d2.
Lấy khoảng cách nhỏ nhất từ hai dãy con (được gọi là d)
Tạo ra một mảng strip[] chứa toàn bộ các điểm mà cách điểm chia (ở bước 2) là <=d.
Tìm khoảng cách nhỏ nhất ở trong strip[] (được gọi là k)
Trả ra kết quả nhỏ nhất trong hai số k và d.
Code minh họa:
class Point
{
public:
int x, y;
};
int compareX(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x - p2->x);
}
int compareY(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y - p2->y);
}
float dist(Point p1, Point p2)
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
float bruteForce(Point P[], int n)
{
float min = FLT_MAX;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
float min(float x, float y)
{
return (x < y)? x : y;
}
float stripClosest(Point strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
qsort(strip, size, sizeof(Point), compareY);
for (int i = 0; i < size; ++i)
for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
if (dist(strip[i],strip[j]) < min)
min = dist(strip[i], strip[j]);
return min;
}
float closestUtil(Point P[], int n)
{
if (n <= 3)
return bruteForce(P, n);
int mid = n/2;
Point midPoint = P[mid];
float dl = closestUtil(P, mid);
float dr = closestUtil(P + mid, n - mid);
float d = min(dl, dr);
Point strip[n];
int j = 0;
for (int i = 0; i < n; i++)
if (abs(P[i].x - midPoint.x) < d)
strip[j] = P[i], j++;
return min(d, stripClosest(strip, j, d) );
}
float closest(Point P[], int n)
{
qsort(P, n, sizeof(Point), compareX);
return closestUtil(P, n);
}
5. Discussion questions
Lấy ví dụ về worst case và best case của quick sort.
Giải thích vì sao độ phức tạp best case của thuật toán quick sort là O(nlogn) và trung bình cũng là O(nlogn).
Vì sao độ phức tạp best case của quick sort là O(nlogn) và độ phức tạp của merge sort, heap sort luôn luôn là O(nlogn) mà quicksort lại có thể nhanh hơn?
Theo bạn, thuật toán sắp xếp nào được dùng khi sử dụng các hàm sắp xếp của thư viện? Và vì sao?
Lấy ví dụ thực tế bạn đã áp dụng chia để trị. Giải thích bạn đã chia, trị và combine như thế nào?
Đăng nhận xét