मैट्रिक्स सॉर्टिंग के लिए निचली बाउंड कैसे मिल सकती है?

Question

n x n मैट्रिक्स को क्रमबद्ध करने की समस्या पर विचार करें (यानी पंक्तियां और कॉलम आरोही क्रम में हैं)। मैं इस समस्या के निचले और ऊपरी बाउंड को ढूंढना चाहता हूं।

मैंने पाया कि यह सिर्फ तत्वों छंटाई और तो पहली पंक्ति के रूप में पहली n तत्वों, दूसरी पंक्ति के रूप में अगले n तत्वों, और इतने पर outputting द्वारा O(n^2 log n) है। हालांकि मैं यह साबित करना चाहता हूं कि यह Omega(n^2 log n) भी है।

छोटे उदाहरण की कोशिश के बाद, मुझे लगता है कि मैं साबित करना चाहिए कि अगर मैं इस समस्या को कम से कम n^2 log(n/e) तुलना का उपयोग कर हल कर सकते हैं, यह होगा log(m!) कम m तत्वों को सॉर्ट करने के लिए आवश्यक तुलना के लिए बाध्य उल्लंघन करती है।

इसे साबित करने के तरीके पर कोई विचार?

Answer 1

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms पर एक नज़र डालें।

आपकी समस्या यह है कि आप सिर्फ n के बजाय n² तत्वों को सॉर्ट कर रहे हैं, इसलिए 'ओ (एन² लॉग एन²)' उदाहरण के लिए विलय के लिए मान्य हो सकता है।

यदि पहली पंक्ति में पहले एन तत्वों को स्वयं को हल करने की आवश्यकता नहीं है तो यह तेज़ हो सकता है, लेकिन असफल नहीं, यह एल्गोरिदम पर निर्भर करता है।

अंतिम लेकिन कम से कम नहीं, कुछ उदाहरणों का प्रयास करना कुछ साबित नहीं होता है, विशेष रूप से छोटे जहां आंकड़े प्रभावी नहीं होते हैं (, वे कुछ भी इंगित नहीं कर रहे हैं)