आकार n के इनपुट के लिए, जिसके लिए एन के मान सम्मिलन-सॉर्ट बीट मर्ज-सॉर्ट करते हैं?

Question

पुस्तक में एल्गोरिदम (कॉर्मन) का परिचय, व्यायाम 1.2-2 सम्मिलन प्रकार के कार्यान्वयन की तुलना करने और क्रमबद्ध करने के बारे में निम्नलिखित प्रश्न पूछता है। आकार n के इनपुट के लिए, प्रविष्टि क्रम 8n^2 चरणों में चलता है जबकि 646 एलजी एन चरणों में सॉर्ट रन चलाता है; जिसके लिए एन के मूल्य प्रविष्टि सॉर्ट विलय विलय करता है?

हालांकि मुझे जवाब में रूचि है, मुझे चरण में उत्तर चरण कैसे प्राप्त करना है, इस बारे में अधिक रुचि है (ताकि मैं संभवतः किसी भी दो दिए गए एल्गोरिदम की तुलना करने के लिए प्रक्रिया को दोहरा सकता हूं)।

पहली नज़र में, यह समस्या बिजनेस-कैलकुस में एक ब्रेक ढूंढने जैसी चीज़ जैसा दिखती है, एक वर्ग जिसे मैंने 5 साल पहले लिया था, लेकिन मुझे यकीन नहीं है कि किसी भी मदद की सराहना की जाएगी।

धन्यवाद

पी/एस मेरे टैग गलत हैं, तो इस सवाल का गलत ढंग से वर्गीकृत किया गया है, या कुछ अन्य सम्मेलन के रूप में यहाँ के साथ दुर्व्यवहार किया जा रहा है कम से कम विलापस्वरूप सीमित करें, यह मेरा पहला समय एक प्रश्न पोस्ट कर रहा है।

Answer 1

आप जब प्रविष्टि तरह धड़क रहा तरह

8n^2<=64nlogn 
n^2<=8nlogn 
n<=8logn 

n-8logn = 0 को सुलझाने पर विलय आप

n = 43.411 

तो n<=43 के लिए प्रविष्टि प्रकार मर्ज प्रकार की तुलना में बेहतर काम करता है मिल लगाने के लिए कर रहे हैं के बाद से।