15
के साथ सॉर्ट करने का समय चल रहा है मान लीजिए कि आपके पास ब्लैक-बॉक्स सबराउटिन था जो (log n)^a समय में एन तत्वों की सरणी से अधिकतम निकालने में सक्षम हो सकता है, जहां 0 <= a <= 1। आप एक इष्टतम सॉर्टिंग एल्गोरिदम बनाने की कोशिश कर रहे हैं जो इस सबराउटिन का उपयोग करता है।ब्लैक-बॉक्स findmax subroutine
स्पष्ट समाधान पूरे सरणी पर सबराउटिन को कॉल करना है, अंतिम तत्व के साथ अधिकतम स्वैप करना है, और फिर उप-दिनचर्या को A[1, n-1] पर A[1, 2] पर कॉल करें।
क्या कोई बेहतर एल्गोरिदम है जो समय से तेज़ चलता है, या स्पष्ट समाधान इष्टतम है?
पहला अवलोकन: यदि आप ब्लैक बॉक्स अधिकतम दिनचर्या –
का उपयोग नहीं करते हैं तो आप बेहतर नहीं कर सकते हैं। – user666866
उन्होंने यह नहीं कहा कि आपके पास वस्तुओं की तुलना करने का एक बेहतर तरीका है। –