Sau khi số đầu tiên của stream là 5 là median là 5
…….số thứ 2…………….. là 15, dãy số 5 , 15 là median là 10
…….số thứ 3 …. Là 1,dãy số 5,15,1 và median là 5
…….số thứ 4….là 3, dãy số là 5,15,1,3 và median là 4
Lưu ý: Cần sắp xếp trước khi tìm median. Output là median của dãy số interger đọc từ stream.
Một thuật toán như thế gọi là online algorithm.
" Any algorithm that can guarantee output of i-elements after processing i-th element, is said to be online algorithm "( Các định nghĩa luôn được giữ nguyên bảng bằng tiếng anh).
Có 3 solutions cho problem trên, chúng ta bắt đầu với giải pháp đầu tiên:
Method 1: Tư tưởng thuật toán insertion sort
Tóm tắt nội dung thuật toán insertion sort: Thuật toán này giả định ta có 1 nhóm phần tử đầu tiên đã được sắp xếp, ta lần lượt chèn các phần tử còn lại vào nhóm phần tử trên.
Ban đầu, nhóm phần tử đó chỉ là phần tử đầu tiên của dãy. Lập lần 1, ta chèn phần tử thứ 2 vào nhóm trên sao cho phù hợp, ta có số lượng của nhóm phần tử đầu tiên là 2, lập lần 3, ta số lượng nhóm phần tử đầu tiên là 3, cứ như thế lập n-1 lần ( với n là số lượng phần tử của dãy số ban đầu) thì ta có được danh sách đã được sắp.
Quay trở lại problem trên, nếu ta có thể sắp xếp data ngay khi nó xuất hiện, chúng ta có thể dễ dàng xác định được median. Insertion sort là 1 online algorithm mà sắp xếp data ngay khi nó xuất hiện.
Ta thấy rằng sau khi sắp xếp element thứ i, i elements của mảng thì được sắp xếp. Insertion sort không phụ thuộc vào data tương lai. Điều này làm nó được gọi là online algorithm.
Tuy nhiên, insertion sort mất O(n^2) để sắp xếp n elements. Có lẽ chúng ta có thể dùng binary search trên insertion sort để vị trí của element kế tiếp trong time O(nlogn).
Tuy vậy, chúng ta không thể làm vậy để duy chuyển data trong time O(nlogn).
Nó mất polynomial time trong trường hợp insertion sort.
Implement: Full python code
Time complexity: O(n^2)
Mong nhận được đóng góp từ bạn đọc.
Xin chân thành cảm ơn !
Edit bye me_BNT
Không có nhận xét nào:
Đăng nhận xét