Medians and Order Statistics

Phần này có 1 vài vấn đề cần quan tâm như:
- Median
- i-th order statistic
 - Selection problem
 -------
1, i-th order statistic
i-th order statistic là phần tử có thứ tự i trong dãy đã xếp hay còn gọi là phần tử nhỏ thứ i trong dãy.
Median( theo môn MAS có thể dịch là trung vị) là phần tử halfway.
Nếu n lẻ, median nằm ở giữa.
Nếu n chẵn, sẽ có median upper và median lower:

 Phát biểu bài toán:
Input: Cho một dãy n phần tử phân biệt và số i (1<=i <= n)
Output: Đưa ra phần tử lớn hơn chính xác i-1 phần tử khác trong dãy. (Nói cách khác đưa ra phần tử nhỏ thứ i trong dãy).

Xét bài toàn tìm minimum và maximum trong một dãy chưa được sort, ta mất (n-1) phép so sánh cho từng loại. Vậy ta phải mất 2n-2 phép so sánh để tìm cả max và min. Liệu có cách nào hiệu quả hơn?
Ta có thể chỉ mất 3*|n/2| phép so sánh bằng cách:

- Chia thành các cặp phần tử
- So sánh từng cặp với nhau
- Với mỗi cặp lại so sánh với min, max hiện tại
=> Chỉ mất 3 phép so sánh cho mỗi cặp.

Mở rộng: Show that the second smallest of n-elements can be found with n+⌈lgn⌉-2 comparisons in the worst case???
Tìm số nhỏ thứ 2 trong dãy chỉ với n+⌈lgn⌉-2 phép so sánh?

2, Selection problem



Quay lại vấn đề tìm số nhỏ thứ i trong dãy, tư duy của một người bình thường sẽ là sort dãy đã cho rồi đưa ra vị trí cần tìm. Mất O(n log n) cho trung bình một lần sort. Liệu có cách nào chỉ tốn O(n) không?

Chung tư tưởng với quicksort, một thuật toán đã được áp dụng.
Tương tự như quicksort, nhưng ta chỉ phân hoạch và đi về một phía của bên được chọn, thuật toán này được chứng mình thời gian trung bình là O(n), nhưng trong trường hợp xấu nhất thì vẫn là O(n^2).

Khi đó, thuật toán median-of-median ra đời để khắc phục tường hợp xấu nhất này.


- Người ta chia thành các nhóm 5 phần tử
- Việc sắp xếp 1 nhóm 5 phần tử được coi như O(1)
- Chọn 5 vì:
      + Số lẻ dễ xác định median
      + 3 thì quá nhỏ => không tối ưu
      + 7, 9, ... quá lớn để coi việc sort như O(1)
-  chọn ra median-of-median m

Tiếp tục phân hoạch và tiếp cho đến khi gặp phần tử cần tìm.
Bài toán được chứng minh dù trường hợp xấu nhất vẫn là O(n).


Comments

Post a Comment

Popular posts from this blog

Reflection: Scope Variables

Image
I, Summary There are two types of c variables.      - Local      - Global Local variables:  Variable whose existence is known only to the main program or functions are called local variables. Local variables are declared with in the main program or a function. Global variables:  Variables whose existence is known to the both main() as well as other functions are called global variables. Global variables are declared outside the main() and other functions. Difference between Local and Global c variables:      - Local c variable is declared in functions and blocks, while global c variables are declared outside functions and blocks.      - Local c variables can be accessed only that function and blocks which declared it, while global c variables can be accessed within all program.      - Local c variables when declared not initialized automatically by system you have to decla...
Read more

Những lợi ích của việc dùng email edu cho developer

Image
Sau khi gần kết thúc quá trình học đại học, hắn mới biết được một vài tác dụng to lớn của mail trường, nhân dịp rảnh quá, làm mới cho blog sắp mốc, hắn quyết định note lại những thứ hay ho mà gần đây hắn hóng được :D Do hắn là 1 sinh viên fpt nên bài viết này chủ yếu dựa trên mail fpt.edu.vn :D Mình chỉ review sơ bộ, khi nào có thời gian mình sẽ viết chi tiết cho từng thằng 1.   JetBrains for Student https://www.jetbrains.com/student/ Cái tài khoản này đăng ký cực kỳ đơn giản, chỉ cần điền mail trường( đuôi .edu) sau đó vào xác nhận mail. Tài khoản student này có giá trị sử dụng 1 năm kể từ ngày đăng ký, khá nhiều tool hay ho để nghịch, lại còn ko phải đăng ký bằng thẻ visa nữa chứ. Mình có dùng key này để active PhpStorm vs PyCharm :))) free 1 năm cơ mà :D 2.   Github Student Developer Pack   Cái gói student này của github thì khá nổi tiếng mà mãi sau này mình mới biết :))) Gói này có quá nhiều tool mà mình cũng chưa nghịch hết, nên chỉ ...
Read more

Reflection: Pointer

Image
I, Summary What is pointer? Pointers are the container/variable who holds address of other variables. C uses pointers in three different ways:      - C uses pointers to create dynamic data structures -- data structures built up from blocks of memory allocated from the heap at run-time.      - C uses pointers to handle variable parameters passed to functions.      - Pointers in C provide an alternative way to access information stored in arrays. Pointer techniques are especially valuable when you work with strings. There is an intimate link between arrays and pointers in C. The declaration of pointers follows this format: type * name;  II, Applied to solve problems 1. void input(int*n, int*m); – input and check n>0, m>0 2. int fun2(int n, int m); Function returns n! + m n if n > 0 and m > 0, otherwise return 0 3. double fun6(int n); Function returns value calculated by formula 4. i...
Read more