एक अनुरक्षित सरणी के औसत को ढूंढना

Question

एक अनुरक्षित सरणी के माध्य को खोजने के लिए, हम एन तत्वों के लिए ओ (nlogn) समय में एक न्यूनतम-ढेर बना सकते हैं, और फिर हम एक को एक/2 तत्वों को निकालने के लिए निकाल सकते हैं मध्यस्थ। लेकिन यह दृष्टिकोण ओ (nlogn) समय ले जाएगा।

क्या हम ओ (एन) समय में कुछ विधि से ऐसा कर सकते हैं? यदि हम कर सकते हैं, तो कृपया कुछ विधि बताएं या सुझाव दें।

Answer 1

आप रैखिक समय में एक अनुरक्षित सरणी के औसत को खोजने के लिए Median of Medians एल्गोरिदम का उपयोग कर सकते हैं।

Answer 2

Quickselect ओ (एन) में काम करता है, यह क्विक्सोर्ट के विभाजन चरण में भी प्रयोग किया जाता है।

Answer 3

यह ओ (एन) में क्विकसेलेक्ट एल्गोरिदम का उपयोग करके किया जा सकता है, केथ ऑर्डर आंकड़े (यादृच्छिक एल्गोरिदम) देखें।

Answer 4

त्वरित चयन एल्गोरिदम रैखिक (O(n)) चलने वाले समय में किसी सरणी के के-वें सबसे छोटे तत्व को पा सकता है। यहाँ अजगर में एक कार्यान्वयन है:

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

विकिपीडिया कहते हैं, माध्य-Medians की ओ (एन) सैद्धांतिक रूप से है, लेकिन यह व्यवहार में उपयोग नहीं किया जाता है क्योंकि "अच्छा" pivots पाने की भूमि के ऊपर यह बहुत धीमी गति से बनाता है । ,

/** 
* 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; 
} 

मैं तुलना और स्वैप तरीकों का स्रोत शामिल नहीं किया है तो यह करना आसान है:
http://en.wikipedia.org/wiki/Selection_algorithm

यहाँ एक Quickselect एल्गोरिथ्म एक सरणी में k'th तत्व को खोजने के लिए के लिए जावा स्रोत है डबल [] के बजाय ऑब्जेक्ट [] के साथ काम करने के लिए कोड को बदलें।

प्रैक्टिस में, आप उपर्युक्त कोड ओ (एन) होने की उम्मीद कर सकते हैं।

Answer 6

मैंने पहले ही मेडिसियन एल्गोरिदम के मध्य के बाद से @dasblinkenlight जवाब को उखाड़ फेंक दिया है, वास्तव में ओ (एन) समय में इस समस्या को हल करता है। मैं केवल यह जोड़ना चाहता हूं कि ढेर का उपयोग करके ओ (एन) समय में इस समस्या को हल किया जा सके। नीचे ढेर का उपयोग करके ओ (एन) समय में एक ढेर का निर्माण किया जा सकता है। विस्तृत विवरण Heap sort

मान लीजिए कि आपके सरणी में एन तत्व हैं, आपको दो ढेर बनाना होगा: एक मैक्सहेप जिसमें पहले एन/2 तत्व (या (एन/2) +1 हैं यदि एन विषम है) और एक मिनीहेप जिसमें शेष तत्व शामिल हैं। यदि एन अजीब है तो आपका औसत अधिकतम प्राप्त करके मैक्सहेप (ओ (1) का अधिकतम तत्व है)। यदि एन भी है, तो आपका औसत है (MaxHeap.max() + MinHeap.min())/2 यह ओ (1) भी लेता है। इस प्रकार, पूरे ऑपरेशन की वास्तविक लागत हेप बिल्डिंग ऑपरेशन है जो ओ (एन) है।

बीटीडब्ल्यू यह मैक्सहेप/मिनहेप एल्गोरिदम भी काम करता है जब आप पहले से सरणी तत्वों की संख्या नहीं जानते हैं (यदि आपको उदाहरण के लिए पूर्णांक की धारा के लिए एक ही समस्या को हल करना है)। आप निम्न आलेख में इस समस्या को हल करने के तरीके के बारे में अधिक जानकारी देख सकते हैं Median Of integer streams