Problem-13

Trong Vấn đề-12, chúng tôi đã chia mảng đầu vào thành các nhóm gồm 5 phần tử. Hằng số 5 đóng một vai trò quan trọng trong phân tích. Chúng ta có thể chia thành nhóm 3 phần tử mà vẫn cho kết quả trong thời gian tuyến tính không?

Solution: Trong trường hợp này, việc sửa đổi nhóm 3 phần tử thay vì 5 khiến quy trình mất nhiều thời gian hơn tuyến tính. Trong trường hợp xấu nhất, ít nhất một nửa số trung vị được tìm thấy trong nhóm lớn hơn median of medians m, nhưng hai trong số các nhóm đó đóng góp ít hơn hai phần tử lớn hơn m. Vì vậy, với giới hạn trên, số lượng phần tử lớn hơn điểm xoay tối thiểu là:

Tương tự như vậy đây là một giới hạn dưới. Sẽ có

các phần tử được đưa vào lệnh gọi đệ quy tới Select. Bước đệ quy tìm median of medians chạy trên từng tập có kích thước và do đó, thời gian lặp lại là:

Giả sử rằng T(n) là hàm số tăng đơn điệu, chúng ta có thể kết luận rằng

và chúng ta có thể nói giới hạn trên cho điều này là

đó là O(nlogn). Do đó, chúng ta không chọn 3 làm kích thước của nhóm.

Problem-14

Như trong Problem-13, chúng ta có thể sử dụng các nhóm có kích thước 7 không?

Solution: Trong trường hợp xấu nhất, ít nhất một nửa trong số trung vị trong các nhóm lớn hơn median of medians m nhưng hai trong số các nhóm đó đóng góp ít hơn bốn phần tử lớn hơn m. Vì vậy, với giới hạn trên, số lượng phần tử lớn hơn pivotpoint tối thiểu là:

Tương tự như vậy đây là một giới hạn dưới. Sẽ có

các phần tử được đưa vào lệnh gọi đệ quy Select. Bước đệ quy tìm trung vị của trung vị chạy trên mỗi nhóm có kích thước n/7 và do đó, thời gian đệ quy là

Điều này được giới hạn ở trên bởi $(a + c) n$ với điều kiện là $c \frac { n } { 7 } - 9c \geq 0$. Do đó, chúng ta có thể chọn 7 làm kích thước nhóm.
(Công thức trên mình cũng chưa hiểu tại sao 8c lại thành 9c, có thể tác giả viết nhầm hoặc có ý nghĩa gì khác mà mình chưa hiểu. Về cơ bản, tác giả đã biến đổi biểu thức thành một phép trừ mà cả 2 phần đều phụ thuộc vào n. Với điều kiện $c \frac { n } { 7 } - 9c \geq 0$ như trên thì chỉ cần $n \geq 9*7=63$ sẽ thỏa mãn yêu cần tìm kiếm tuyến tính nếu sử dụng kích thước 7)

Problem-15

Cho hai mảng, mỗi mảng chứa n phần tử được sắp xếp, hãy đưa ra thuật toán thời gian $O(logn)$ để tìm trung vị của tất cả 2n phần tử.

Solution: Giải pháp đơn giản cho vấn đề này là merge hai danh sách rồi lấy giá trị trung bình của hai phần tử ở giữa. Tuy nhiên, merge sẽ cần độ phức tạp $Θ(n)$, vì vậy điều đó không thỏa mãn yêu cầu bài toán. Để có độ phức tạp $O(logn)$, hãy đặt medianA và medianB là trung vị của các danh sách tương ứng (có thể dễ dàng tìm thấy vì cả hai danh sách đều được sắp xếp). Nếu medianA == medianB, thì đó là trung vị tổng thể của 2 list, công việc hoàn thành. Nếu không, trung vị của 2 list phải nằm giữa 2 trung vị A và B. Giả sử medianA < medianB (trường hợp ngược lại hoàn toàn tương tự). Khi đó ta cần tìm trung tuyến của hợp của hai tập hợp sau:

Vì vậy, chúng ta có thể thực hiện điều này một cách đệ quy bằng cách đặt lại ranh giới của hai mảng. Thuật toán sẽ theo dõi cả hai mảng (được sắp xếp) bằng hai chỉ số. Các chỉ số này được sử dụng để truy cập và so sánh giá trị trung bình của cả hai mảng để tìm ra vị trí của giá trị trung bình tổng thể.

Code mình tham khảo ở đây, cách này còn gọi là Binary Search Approach(Trong code đang là bài toán 2 danh sách có độ dài khác nhau m, n)

static float MO2(int a, int b) {
        return (float) ((a + b) / 2.0);
    }
 
    static float MO3(int a, int b, int c) {
        return a + b + c - Math.max(a, Math.max(b, c)) -
          Math.min(a, Math.min(b, c));
    }
    static float MO4(int a, int b, int c, int d) {
        int Max = Math.max(a, Math.max(b, Math.max(c, d)));
        int Min = Math.min(a, Math.min(b, Math.min(c, d)));
        return (float) ((a + b + c + d - Max - Min) / 2.0);
    }
    static float medianSingle(int arr[], int n) {
        if (n == 0)
            return -1;
        if (n % 2 == 0)
            return (float) ((double) (arr[n / 2] +
                                      arr[n / 2 - 1]) / 2);
        return arr[n / 2];
    }
    static float findMedianUtil(int A[], int N, int B[], int M) {
        if (N == 0)
            return medianSingle(B, M);
 
        if (N == 1) {
            if (M == 1)
                return MO2(A[0], B[0]);
 
            if (M % 2 == 1)
                return MO2(B[M / 2], (int) MO3(A[0],
                            B[M / 2 - 1], B[M / 2 + 1]));
 
            return MO3(B[M / 2], B[M / 2 - 1], A[0]);
        }
        else if (N == 2) {
            if (M == 2)
                return MO4(A[0], A[1], B[0], B[1]);
 
            
            if (M % 2 == 1)
                return MO3(B[M / 2], Math.max(A[0], B[M / 2 - 1]),
                           Math.min(A[1], B[M / 2 + 1]));
 
            
            return MO4(B[M / 2], B[M / 2 - 1],
                       Math.max(A[0], B[M / 2 - 2]),
                       Math.min(A[1], B[M / 2 + 1]));
        }
 
        int idxA = (N - 1) / 2;
        int idxB = (M - 1) / 2;
        if (A[idxA] <= B[idxB])
            return findMedianUtil(Arrays.copyOfRange(A, idxA, A.length),
                                  N / 2 + 1, B, M - idxA);
 
       
        return findMedianUtil(A, N / 2 + 1,
               Arrays.copyOfRange(B, idxB, B.length), M - idxA);
    }
    static float findMedian(int A[], int N, int B[], int M)
    {
        if (N > M)
            return findMedianUtil(B, M, A, N);
 
        return findMedianUtil(A, N, B, M);
    }

Time Complexity: $O(logn)$(Với m =n), vì chúng ta đang giảm một nửa kích thước của bài toán mỗi lần đệ quy.

Problem-16

Cho A và B là hai dãy đã sắp xếp mỗi dãy có n phần tử. Chúng ta có thể dễ dàng tìm thấy phần tử nhỏ thứ k trong A trong thời gian O(1) bằng cách chỉ xuất ra A[k]. Tương tự ta dễ dàng tìm được phần tử nhỏ thứ k trong B. Đưa ra thuật toán thời gian O(logk) để tìm phần tử nhỏ thứ k trong hợp của A và B.

Solution: Bài toán tương tự Problem-15, chỉ khác là mỗi mảng sẽ lấy k phần tử đầu tiên. Khi hợp lại 2 mảng sẽ có độ dài 2k, trung vị chính là phần tử nhỏ thứ k cần tìm.

Problem-17

Cho một tập hợp gồm n phần tử cho trước, hãy tìm k phần tử nhỏ nhất và liệt kê chúng theo thứ tự đã sắp xếp. Phân tích thời gian chạy trong trường hợp xấu nhất để triển khai phương pháp tốt nhất.

Solution: Sắp xếp và liệt kê k phần tử nhỏ nhất.

$T(n) =$ Thời gian để sắp xếp + Thời gian để liệt kê k phần tử nhỏ nhất $= Θ(n logn) + Θ(n) = Θ(n logn).$

Problem-18

Đối với Problem-17, hãy tìm cách khác.

Solution: Sử dụng cấu trúc dữ liệu hàng đợi ưu tiên từ heap sort, xây dựng một min-heap trên tập hợp và thực hiện gọi phần tử nhỏ nhất k lần. Các bạn có thể xem lại bài viết này.

Problem-19

Đối với Problem-17, hãy tìm cách khác.

Solution: Sử dụng kĩ thuật phân vùng để lấy ra k phần tử nhỏ nhất, sau đó sắp xếp chúng.

Vì, k ≤ n, cách tiếp cận này tốt hơn Problem-17 và Problem-18.

Note: Để có thời gian chỉ O(n) khi tìm phần tử nhỏ thứ k(Các bạn có thể xem lại Problem-12), khi tìm được pivotpoint này rồi, việc phân vùng k phần tử nhỏ nhất cũng sẽ chỉ mất O(n).

Problem-20

Problem-21

Problem 20 và 21 liên quan tới bài toán tìm k phần tử hàng xóm gần nhất, trong sách tác giả viết khá chung chung, các bạn có thể tham khảo thêm ở đây