एन संख्याओं का सबसे बड़ा और दूसरा सबसे बड़ा पता

Question

एन संख्याओं को देखते हुए, मुझे सबसे अधिक एन + लॉग (एन) तुलनाओं का उपयोग करके सबसे बड़ा और दूसरा सबसे बड़ा नंबर कैसे मिलता है?

ध्यान दें कि यह ओ (एन + लॉग (एन)) नहीं है, लेकिन वास्तव में एन + लॉग (एन) तुलना है।

Answer 1

पायज़टन ने एक टिप्पणी दी।

मुझे विस्तृत करने दें।

जैसा कि पजटन ने कहा, यह टूर्नामेंट चयन द्वारा किया जा सकता है।

इस बारे में सोचना एकल टेनिस टूर्नामेंट के रूप में सोचें, जहां खिलाड़ी क्षमताओं का सख्त आदेश होता है और एक मैच का नतीजा पूरी तरह से उस आदेश द्वारा तय किया जाता है।

पहले दौर में आधा लोगों को समाप्त कर दिया गया है। अगले दौर में एक और आधा आदि (कुछ बाई संभव के साथ)।

आखिरकार विजेता अंतिम और अंतिम दौर में तय किया जाता है।

इसे एक पेड़ के रूप में देखा जा सकता है।

पेड़ का प्रत्येक नोड उस नोड के बच्चों के बीच मैच का विजेता होगा।

पत्तियां खिलाड़ी हैं। पहले दौर के विजेता पत्तियों आदि के माता-पिता हैं।

यह एन नोड्स पर एक पूर्ण बाइनरी पेड़ है।

अब विजेता के मार्ग का पालन करें। विजेता के खेले गए लॉग एन मैच हैं। अब उन लॉग एन मैचों के हारने वालों पर विचार करें। दूसरा सबसे अच्छा उन लोगों में सबसे अच्छा होना चाहिए।

विजेता का निर्णय एन -1 मैचों में किया जाता है (आप प्रति मैच एक मैच आउट करते हैं) और लॉग इन के बीच विजेता लॉग -1 -1 मैचों में तय किया जाता है।

इस प्रकार आप एन + लॉगन -2 तुलना में सबसे बड़ा और दूसरा सबसे बड़ा निर्णय ले सकते हैं।

वास्तव में, यह साबित कर सकता है कि यह इष्टतम है। सबसे खराब मामले में किसी तुलनात्मक योजना में, विजेता को लॉग इन मैच खेलना होगा।

यह साबित करने के लिए कि एक बिंदु प्रणाली मान लीजिए जहां एक मैच के बाद विजेता हारने वालों के अंक प्राप्त करता है। शुरुआत में सभी 1 बिंदु प्रत्येक के साथ शुरू करते हैं।

अंत में अंतिम विजेता के पास अंक हैं।

अब कोई भी एल्गोरिदम दिया गया है, इसे व्यवस्थित किया जा सकता है ताकि अधिक अंक वाले खिलाड़ी हमेशा विजेता हों। चूंकि किसी भी व्यक्ति के बिंदु उस परिदृश्य में किसी भी मैच में सबसे अधिक दोगुना है, इसलिए आपको सबसे खराब मामले में विजेता द्वारा खेले जाने वाले कम से कम लॉग एन मैचों की आवश्यकता होती है।

Answer 2

क्या इसमें कोई समस्या है? यह अधिकतम 3 एन तुलनाओं पर है (i < n तुलना की गणना नहीं)। यदि आप इसे गिनते हैं, तो यह 4 एन (या दूसरे उदाहरण में 5 एन) है।

double first = -1e300, second = -1e300; 
for (i = 0; i < n; i++){ 
    if (a[i] > first){ 
    second = first; 
    first = a[i]; 
    } 
    else if (a[i] > second && a[i] < first){ 
    second = a[i]; 
    } 
} 

एक और तरीका यह कोड करने के लिए:

for (i = 0; i < n; i++) if (a[i] > first) first = a[i]; 
for (i = 0; i < n; i++) if (a[i] < first && a[i] > second) second = a[i];