ओ (लॉग एन)

Question

में क्रमबद्ध मैट्रिक्स (पंक्तियां एन कॉलम) में संख्या खोजें कहें कि मेरे पास एक मैट्रिक्स (MxN) है जिसमें इसकी पंक्तियां और कॉलम क्रमबद्ध हैं।

1. सभी प्रत्येक पंक्ति में तत्वों बढ़ते क्रम में व्यवस्थित कर रहे हैं बढते क्रम
2. में
प्रत्येक स्तंभ में
3. सभी तत्वों को व्यवस्थित कर रहे हैं सभी तत्वों पूर्णांकों

4. कोई अन्य मान्यताओं

   की जा सकती हैं

   उदाहरण:

   [1 5 से 8 20]

   [2 9 19 21]

   [12 15 25 30]

मैं अगर दी गई संख्या या मैट्रिक्स में मौजूद (बेसिक खोज) नहीं है खोजने के लिए। मैं एक एल्गोरिथ्म जो O(n)

int row = 0; 
int col = N-1; 

while (row < M && col >= 0) { 
    if (mat[row][col] == elem) { 
    return true; 
    } else if (mat[row][col] > elem) { 
    col--; 
    } else { 
    row++; 
    } 
} 

चलाता है लेकिन मैं एक O(log (MxN)) == O(Log(n)) समाधान कहा गया। कोई विचार??

Answer 1

ओ (लॉग (एम * एन)) समाधान इस कार्य के लिए संभव नहीं है।

चलिए एक सरलीकृत कार्य को देखते हैं: "क्रमबद्ध" वर्ग मैट्रिक्स में दिए गए नंबर से कम माध्यमिक विकर्ण (हरा) से ऊपर के सभी तत्वों को मानते हैं, दिए गए संख्या से अधिक माध्यमिक विकर्ण (लाल) से नीचे सभी तत्व, और तत्वों के लिए कोई अतिरिक्त धारणा नहीं माध्यमिक विकर्ण (पीला) पर।

न तो इस कार्य के मूल मान्यताओं, और न ही इन अतिरिक्त मान्यताओं पूछा कि वह कैसा माध्यमिक विकर्ण पर तत्व एक दूसरे से जुड़े हुए हैं। जिसका अर्थ है कि हमारे पास एन पूर्णांक की एक अनारक्षित सरणी है। हम ओ (एन) की तुलना में निरस्त सरणी में दिए गए नंबर को नहीं ढूंढ सकते हैं। तो स्क्वायर मैट्रिक्स के साथ मूल (अधिक जटिल) समस्या के लिए हम ओ (एन) से बेहतर समाधान नहीं प्राप्त कर सकते हैं।

एक आयताकार मैट्रिक्स के लिए, वर्ग चित्र को फैलाएं और तदनुसार अतिरिक्त मान्यताओं को सेट करें। यहां हमारे पास न्यूनतम (एन, एम) आकार अधिकतम (एन, एम)/मिनट (एन, एम) के उप-सरणी क्रमबद्ध हैं। यहां खोज करने का सबसे अच्छा तरीका एक या कई सब-एरे खोजने के लिए रैखिक खोज का उपयोग करना है जिसमें दिए गए मान हो सकते हैं, फिर इन उप-सरणी के अंदर बाइनरी खोज का उपयोग करें। सबसे खराब स्थिति में प्रत्येक उप-सरणी में बाइनरी-सर्च करना आवश्यक है। जटिलता ओ है (न्यूनतम (एन, एम) * (1 + लॉग (अधिकतम (एन, एम)/मिनट (एन, एम)))। तो आयताकार मैट्रिक्स के साथ मूल (अधिक जटिल) समस्या के लिए हम ओ (न्यूनतम (एन, एम) * (1 + लॉग (अधिकतम (एन, एम)) से बेहतर समाधान नहीं प्राप्त कर सकते हैं - लॉग (न्यूनतम (एन, एम))))।

Answer 2

चूंकि दोनों पंक्तियों और स्तंभों को क्रमबद्ध किया जाता है, यदि हम प्रत्येक पंक्ति के पहले तत्व को देखते हैं तो हम पाते हैं कि हम किस नंबर को खोज रहे हैं। फिर, फिर, हम इस तथ्य का फायदा उठा सकते हैं कि प्रत्येक पंक्ति में तत्वों को क्रमबद्ध किया जाता है और वह संख्या मिलती है।
सबसे तेज़ खोज एल्गोरिदम मुझे पता है बाइनरी सर्च, जिसमें ओ (लॉग एन) की जटिलता है, इसलिए कुल जटिलता ओ (लॉग एम + लॉग एन) होगी।
यहाँ एक उदाहरण है, मान लीजिए हम 28 के लिए देख रहे:

1 2 3 4 5 6 7 8 9 10 
11 12 13 14 15 16 17 18 19 20 
21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 49 50 

• हम पहले कॉलम (1, 11, 21, 31, 41) के तत्वों के ऊपर एक द्विआधारी खोज करते हैं और पाते हैं कि पंक्ति तीसरी है, क्योंकि इसका पहला तत्व हमारे नंबर से छोटा है लेकिन अगली पंक्ति का पहला तत्व बड़ा है। चरणों की संख्या: 2 (21, 31, मिला)
• हम तीसरी पंक्ति (21, 22, 23, 24, 25, 26, 27, 28, 2 9, 30) पर फिर से एक बाइनरी खोज करते हैं और पाते हैं हमारी संख्या चरणों की संख्या: 2 - 3 (25, 27 या 28 में पाया गया)

Answer 3

आप इस समस्या को हल करने के लिए प्रत्यावर्तन उपयोग करना होगा। एक मैट्रिक्स एक्स और संख्या y देखते हुए, आप एक्स के मध्य पंक्ति पर y के लिए द्विआधारी खोज करते हैं और चार भागों ऐसी है कि में मैट्रिक्स विभाजित कर सकते हैं:

A|B 
--- 
C|D 

एक में सभी तत्वों y से कम हैं, सभी तत्वों डी में वाई से अधिक हैं, और वाई बी और सी में हो सकते हैं Iterly बी और सी

ऊंचाई (ए) = ऊंचाई (बी) \ लगभग = ऊंचाई (सी) = ऊंचाई (डी) , आकार (एक्स)> = 2 * (आकार (बी) + आकार (सी))। तो परिणामस्वरूप जटिलता अगर ओ (लॉगन)।

def find(X,y): 
    a,b = X.shape 
    i = a /2 
    j = binsearch(X[i,:], y) 
    if X[i,j]==y: 
     return True 
    else: 
     return find(X[ (i+1):a, 0:(j-1)], y) or find(X[ 0:i, j:b], y) 

Answer 4

ओ (एन) से बेहतर करना संभव नहीं है।कुछ लोग (इस पृष्ठ पर उनमें से कम से कम तीन हैं) लगता है कि वे बेहतर कर सकते हैं लेकिन ऐसा इसलिए है क्योंकि उनके एल्गोरिदम गलत हैं या क्योंकि वे नहीं जानते कि उनके एल्गोरिदम की जटिलता की गणना कैसे करें ताकि वे इसे अनुमान लगाने का प्रयास करें। This blog post बहुत अच्छा है और आपको इन लोगों की त्रुटियों की व्याख्या करेगा। एक सबूत के

ड्राफ्ट कि हे (एन) इष्टतम है: निम्नलिखित मैट्रिक्स पर विचार करें:

1  2  3  4  5  6 … (n-2) (n-1) (n+1) 
2  3  4  5  6  7 … (n-1) (n+1) (n+2) 
3  4  5  6  7  8 … (n+1) (n+2) (n+3) 
…  …  …  …  …  … … …  …  … 
(n-2) (n-1) …  …  …  … … …  …  (2n-1) 
(n-1) (n+1) …  …  …  … … …  …  2n 
(n+1) (n+2) …  …  …  … … (2n-1) 2n (2n+1) 

आप इस मैट्रिक्स में देख रहे हैं n के लिए आप प्रत्येक पंक्ति के लिए कम से कम एक बार जांच करना चाहिए अगर n में है पंक्ति क्योंकि n किसी भी पंक्ति में हो सकती है। (सबूत पूरा नहीं हुआ है लेकिन यहां विचार है)

Answer 5

मुझे लगता है कि यह ओ (लॉग (एन * एन) * लॉग (एन)) समय में किया जा सकता है, जहां एन नंबर है। एक वर्ग मैट्रिक्स की पंक्तियों का।

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

अब, उप-मैट्रिक्स (शीर्ष-दाएं) में और उप-मैट्रिक्स (निचले बाएं) में पुनः खोज करें।

चूंकि, प्रत्येक चरण में, हम एक लॉग (एन) खोज (प्रिंसिपल विकर्ण के साथ) विज्ञापन करते हैं, वहां लगभग लॉग (एन * एन) चरण हो सकते हैं (क्योंकि हम खोज चरण को प्रत्येक चरण में आधे से कम करते हैं)।

तो, समय जटिलता = ओ (लॉग (एन) लॉग (एन एन))।

यदि कुछ भी गलत है, तो कृपया सही करें।

refrences - [पुस्तक] कोडिंग साक्षात्कार क्रैकिंग (प्रश्न 11.6)