उच्चतम 2 संख्याओं को ढूंढना- कंप्यूटर विज्ञान

Question

मैं संख्याओं की सूची में उच्चतम 2 संख्याओं को खोजने के लिए एक एल्गोरिदम का पता लगाने की कोशिश कर रहा हूं।

उच्चतम संख्या एन -1 चरणों में पाया जा सकता है, शायद एक बबल प्रकार के मुट्ठी चरण या उन पंक्तियों के साथ कुछ कर कर। मेरे लिए ऐसा लगता है कि अगले उच्चतम नंबर को भी औसत पर कुल 1.5 एन तुलना में पाया जा सकता है।

मेरे प्रोफेसर ने हमें एक एल्ग्रिथम लिखने के लिए होमवर्क सेट किया जो एन + लॉग (एन) तुलना में उच्चतम 2 संख्या पाता है। क्या यह भी संभव है? कोई विचार, सुझाव?

संपादित करें: जब मैं कहता n + लॉग ऑन (एन) मैं हे की बात नहीं कर रहा हूँ (n + लॉग इन करें n), बल्कि वास्तव में n + n

Answer 1

हां, इसे (एन + लॉग एन) से अधिक में करना संभव है। मैं वास्तव में आपको बता नहीं सकता कि उत्तर देने के बिना, लेकिन मुझे कोशिश करने दो। :-)

एन संख्याएं लें, एक समय में जोड़े में उनकी तुलना करें। छत (एन/2) "विजेता" लें, और दोहराएं, "एक बाइनरी पेड़ की तरह"। प्रश्न: सबसे बड़ा खोजने के लिए कितनी तुलना होती है? इस "विजेता" के खिलाफ कितने लोग जीतते हैं? दूसरा सबसे बड़ा किसके लिए खो सकता है? तो दूसरी सबसे बड़ी संख्या को खोजने के लिए अब कितनी तुलना की जाती है?

जवाब पता चला है n-1 + छत (लॉग एन) के कुल होना करने के लिए - 1 तुलना, जहां लॉग 2. आधार पर है तुम भी एक विरोधात्मक तर्क का उपयोग यह है कि यह संभव नहीं है साबित कर सकते हैं सबसे खराब मामले में इससे बेहतर करें।

Answer 2

कैसे इस बारे में लॉग इन करें:

for each listOfNumbers as number 
    if number > secondHighest 
     if number > highest 
      secondHighest = highest 
      highest = number 
     else 
      secondHighest = number 

Answer 3

संपादित करें: ओह, मूर्खता के कारण एक साधारण चीज़ याद आती है। यह समाधान सही नहीं है, हालांकि मैं इसे यहां रख रहा हूं क्योंकि यह अभी भी औसत है (एन + लॉग (एन))। मेरी मूर्खता को इंगित करने के लिए श्रीवत्सआर के लिए धन्यवाद। मैंने पेड़ की खोज पर विचार किया, लेकिन लॉग (एन) में दूसरी सबसे बड़ी संख्या को खोजने के लिए बैकट्रैकिंग के विचार को पूरी तरह याद किया।

वैसे भी, यहां मेरे सबूत का पालन किया गया है कि निम्न एल्गोरिदम औसत (एन + लॉग (एन) से अधिक क्यों नहीं है)। वास्तविक जीवन में इसे कम से कम बहुत अच्छा प्रदर्शन करना चाहिए।

• सबसे पहले दर्ज की गई दूसरी उच्चतम दर्ज संख्या के विरुद्ध तुलना करें।
• केवल तभी जब यह तुलना सफल होती है, तो उच्चतम दर्ज की गई संख्या के विरुद्ध तुलना करें।

साबित करने के लिए कि यह औसत एन + लॉग एन पर है, हमें बस यह साबित करना होगा कि पहली तुलना औसत पर लॉग (एन) बार सफल होती है। और यह देखने या प्रदर्शित करने के लिए काफी सरल है।

1. वर्तमान सूची का एक क्रमबद्ध संस्करण में दूसरा सबसे बड़ा संख्या की वास्तविक स्थिति के रूप में पी मान लें, और कलन विधि को चलाने
2. तो P> 2 फिर जब एक बड़ी संख्या में पाया जाता है, नए पी होगा औसतन पी/2 से अधिक नहीं हो।
3. यदि पी = 2 तो पहली तुलना सफल नहीं हो सकती है, क्योंकि वर्तमान नंबर की तुलना में कोई संख्या नहीं है।
4. पी सबसे बराबर एन
5. 2, 3 और 4 से यह देखने के लिए छोटा होना चाहिए कि पहली तुलना औसत पर लॉग (एन) बार से अधिक सफल नहीं हो सकती है।

Answer 4

श्रीवत्सआर द्वारा पोस्ट किया गया उत्तर ओ (एन लॉग एन) लगता है।

पहला पास (एन ऑपरेशंस) एन/2 उत्तरों का उत्पादन करता है। दोहराने से, मुझे लगता है कि आप का मतलब है कि आप एन/4 उत्तरों के उत्पादन के लिए एन/2 ऑपरेशन करेंगे। आप लूप लॉग एन बार के माध्यम से जाना होगा। यह एक विलय प्रकार की तरह बहुत है कि विलय सॉर्ट हमेशा हर बार n nodes को संसाधित करता है। यह लूप लॉग एन बार भी चलाता है। और मैं नहीं देखता कि यह एल्गोरिदम दूसरे higest संख्या का ट्रैक कैसे रखेगा।

निक के पास सही जवाब है। सबसे खराब मामला तब होता है जब सूची क्रमबद्ध होती है, यह 2 एन तुलना करेगा - वह ओ (एन) है।

बीटीडब्ल्यू, ओ (एन + लॉग एन) ओ (एन) ऑर्डर नोटेशन सबसे खराब केस एसिम्प्टोटिक विकास को संदर्भित करता है।

Answer 5

आप गणना क्रम में क्रमबद्ध करने के लिए गिनती सॉर्ट, रेडिक्स सॉर्ट, बाल्टी सॉर्ट या अन्य रैखिक समय एल्गोरिदम का उपयोग कर सकते हैं। फिर बस क्रमबद्ध सूची के पहले 2 तत्व प्राप्त करें। तो यह ले जाएगा (एन) + 2 = (एन)

ध्यान दें कि यह एल्गोरिदम रैखिक समय में क्रमबद्ध हो सकता है क्योंकि प्रत्येक व्यक्ति की अपनी धारणाएं होती हैं।

Answer 6

स्यूडोकोड

int highestNum = 0 
int secondHighest = highestNum 

for(i = 0; i < list.length; i++) 
{ 
if(list[i] >= highestNum) 
{ 
secondHighest = highestNum 
highestNum = list[i] 
} 
}