Tìm giá trị trung bình của mảng chưa phân loại

Question

Để tìm giá trị trung bình của mảng chưa được phân loại, chúng ta có thể tạo một thời gian tối thiểu trong thời gian O (nlogn) cho n phần tử và sau đó chúng ta có thể trích xuất từng phần tử n/2 trung vị. Nhưng cách tiếp cận này sẽ mất thời gian O (nlogn).

Chúng ta có thể thực hiện tương tự bằng một số phương pháp trong thời gian O (n) không? Nếu có thể, hãy nói hoặc đề nghị một số phương pháp.

Answer 1

Bạn có thể sử dụng thuật toán Median of Medians để tìm trung vị của một mảng chưa được phân loại theo thời gian tuyến tính.

Answer 2

Quickselect hoạt động trong O (n), điều này cũng được sử dụng trong bước phân vùng của Quicksort.

Answer 3

Có thể thực hiện bằng thuật toán Quickselect trong O (n), tham khảo số liệu thống kê thứ tự K (thuật toán ngẫu nhiên).

Answer 4

Thuật toán chọn nhanh có thể tìm phần tử nhỏ nhất thứ k của một mảng theo thời gian chạy tuyến tính (O(n)). Đây là một thực hiện trong python:

import random 

def partition(L, v): 
    smaller = [] 
    bigger = [] 
    for val in L: 
     if val < v: smaller += [val] 
     if val > v: bigger += [val] 
    return (smaller, [v], bigger) 

def top_k(L, k): 
    v = L[random.randrange(len(L))] 
    (left, middle, right) = partition(L, v) 
    # middle used below (in place of [v]) for clarity 
    if len(left) == k: return left 
    if len(left)+1 == k: return left + middle 
    if len(left) > k: return top_k(left, k) 
    return left + middle + top_k(right, k - len(left) - len(middle)) 

def median(L): 
    n = len(L) 
    l = top_k(L, n/2 + 1) 
    return max(l) 

Answer 5

Như wikipedia nói, trung bình-of-trung vị là về mặt lý thuyết o (N), nhưng nó không được sử dụng trong thực tế vì các nguyên cần thiết của việc tìm kiếm trụ "tốt" làm cho nó quá chậm .
http://en.wikipedia.org/wiki/Selection_algorithm

Đây là nguồn Java cho một thuật toán Quickselect để tìm các yếu tố k'th trong một mảng:

/** 
* Returns position of k'th largest element of sub-list. 
* 
* @param list list to search, whose sub-list may be shuffled before 
*   returning 
* @param lo first element of sub-list in list 
* @param hi just after last element of sub-list in list 
* @param k 
* @return position of k'th largest element of (possibly shuffled) sub-list. 
*/ 
static int select(double[] list, int lo, int hi, int k) { 
    int n = hi - lo; 
    if (n < 2) 
     return lo; 

    double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot 

    // Triage list to [<pivot][=pivot][>pivot] 
    int nLess = 0, nSame = 0, nMore = 0; 
    int lo3 = lo; 
    int hi3 = hi; 
    while (lo3 < hi3) { 
     double e = list[lo3]; 
     int cmp = compare(e, pivot); 
     if (cmp < 0) { 
      nLess++; 
      lo3++; 
     } else if (cmp > 0) { 
      swap(list, lo3, --hi3); 
      if (nSame > 0) 
       swap(list, hi3, hi3 + nSame); 
      nMore++; 
     } else { 
      nSame++; 
      swap(list, lo3, --hi3); 
     } 
    } 
    assert (nSame > 0); 
    assert (nLess + nSame + nMore == n); 
    assert (list[lo + nLess] == pivot); 
    assert (list[hi - nMore - 1] == pivot); 
    if (k >= n - nMore) 
     return select(list, hi - nMore, hi, k - nLess - nSame); 
    else if (k < nLess) 
     return select(list, lo, lo + nLess, k); 
    return lo + k; 
} 

Tôi chưa bao gồm nguồn gốc của sự so sánh và trao đổi phương pháp, vì vậy nó dễ dàng để thay đổi mã để làm việc với Object [] thay vì double [].

Trong thực tế, bạn có thể mong đợi mã trên là o (N).

Answer 6

Tôi đã upvoted câu trả lời @dasblinkenlight vì thuật toán Median of Medians trong thực tế giải quyết được vấn đề này trong thời gian O (n). Tôi chỉ muốn thêm rằng vấn đề này có thể được giải quyết trong O (n) thời gian bằng cách sử dụng heaps cũng. Xây dựng một đống có thể được thực hiện trong thời gian O (n) bằng cách sử dụng từ dưới lên. Hãy xem bài viết sau đây để biết giải thích chi tiết Heap sort

Giả sử rằng mảng của bạn có N phần tử, bạn phải tạo hai vùng: MaxHeap chứa phần tử N/2 đầu tiên (hoặc (N/2) +1 nếu N là lẻ) và MinHeap chứa các phần tử còn lại. Nếu N là lẻ thì trung bình của bạn là phần tử tối đa của MaxHeap (O (1) bằng cách lấy giá trị cực đại). Nếu N là chẵn, thì trung bình của bạn là (MaxHeap.max() + MinHeap.min())/2 điều này cũng lấy O (1). Do đó, chi phí thực của toàn bộ hoạt động là hoạt động xây dựng heaps là O (n).

BTW Thuật toán MaxHeap/MinHeap này cũng hoạt động khi bạn không biết số phần tử mảng trước (nếu bạn phải giải quyết cùng một vấn đề cho luồng số nguyên ví dụ). Bạn có thể xem thêm chi tiết về cách giải quyết vấn đề này trong bài viết sau Median Of integer streams