पूर्णांक की 2 क्रमबद्ध सरणी के कुशल क्रमबद्ध कार्टेशियन उत्पाद

Question

संकेत एक कुशल एल्गोरिदम तैयार करने के लिए जो निम्न इनपुट लेता है और निम्न आउटपुट को थूकता है।

इनपुट: पूर्णांकों ए और बी के दो क्रमबद्ध सरणियों, लंबाई एन से प्रत्येक

आउटपुट: एक क्रमबद्ध सरणी सरणियों एक की कार्तीय उत्पाद और बी के होते हैं

For Example: 

Input: 
A is 1, 3, 5 
B is 4, 8, 10 
here n is 3. 

Output: 
4, 8, 10, 12, 20, 24, 30, 40, 50 

यहाँ मेरी प्रयास कर रहे हैं इस समस्या को हल करने पर।

1) यह देखते हुए कि आउटपुट एन^2 है, कुशल एल्गोरिदम ओ (एन^2) समय जटिलता से बेहतर नहीं कर सकता है।

2) सबसे पहले मैंने एक सरल लेकिन अक्षम दृष्टिकोण की कोशिश की। ए और बी के कार्टेशियन उत्पाद उत्पन्न करें यह ओ (एन^2) समय जटिलता में किया जा सकता है। हमें स्टोर करने की जरूरत है, इसलिए हम इसे क्रमबद्ध कर सकते हैं। इसलिए ओ (एन^2) अंतरिक्ष जटिलता भी। अब हम एन^2 तत्वों को सॉर्ट करते हैं जिन्हें इनपुट पर कोई धारणा किए बिना ओ (एन^2 लॉग्न) से बेहतर नहीं किया जा सकता है।

अंत में मेरे पास ओ (एन^2 एलोग्न) समय और ओ (एन^2) अंतरिक्ष जटिलता एल्गोरिदम है।

एक बेहतर एल्गोरिदम होना चाहिए क्योंकि मैंने का उपयोग नहीं किया है इनपुट सरणी की प्रकृति को क्रमबद्ध किया है।

Answer 1

अगर वहाँ एक समाधान है कि हे (n ² लॉग n) यह सिर्फ तथ्य यह है कि ए और बी पहले से ही हल कर रहे हैं शोषण अधिक करने की जरूरत है की तुलना में बेहतर है। मेरा जवाब this question पर देखें।

---

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

मान लें कि हमारे पास ए = 6,7,8 और बी = 3,4,5 है। सबसे पहले, बी में पहला तत्व द्वारा एक में हर तत्व गुणा, और एक सूची में इन स्टोर:

6 × 3 = 18, 7 × 3 = 21, 8 × 3 = 24

इस सूची (6 × 3) की सबसे छोटी तत्व का पता लगाएं, उत्पादन, यह उस तत्व के साथ एक समय में अगले तत्व बी में बदल देते हैं:

7 × 3 = 21, 6 × 4 = 24, 8 × 3 = 24

इस सूची (7 × 3), यह उत्पादन के नए सबसे छोटा तत्व खोजें, और बदल देते हैं:

6 × 4 = 24, 8 × 3 = 24, 7 × 4 = 28

और इसी तरह। हमें केवल ओ (एन) इस इंटरमीडिएट सूची के लिए स्थान की आवश्यकता है, और प्रत्येक चरण में सबसे छोटा तत्व ढूंढना ओ (लॉग एन) समय लेता है यदि हम सूची को heap में रखते हैं।

Answer 2

यदि आप बी के सभी मानों के साथ ए के मान को गुणा करते हैं, तो परिणाम सूची अभी भी क्रमबद्ध है। अपने उदाहरण में:

एक 5

बी 4, 8 है 1 है, 3,, 10

1 * (4,8,10) = 4,8,10

3 * (4,8,10) = 12,24,30

अब आप दो सूचियों को विलय कर सकते हैं (बिल्कुल मर्ज सॉर्ट में)। आप बस सूची सूची दोनों को देखें और परिणाम सूची में छोटे को रखें। तो यहां आप 4 का चयन करेंगे, फिर 8 फिर 10 आदि परिणाम = 4,8,10,12,24,30

अब आप परिणाम सूची के लिए वही करते हैं और अगली शेष सूची 4,8,10 विलय , 5,24,30 5 * (4,8,10) = 20,40,50 के साथ।

विलय के रूप में विलय करना सबसे प्रभावी है यदि दोनों सूचियों में समान लंबाई है, तो आप दो हिस्सों में ए को विभाजित करके उस स्कीमा को संशोधित कर सकते हैं, दोनों भागों के लिए आवर्ती रूप से विलय कर सकते हैं, और दोनों परिणामों को मर्ज कर सकते हैं।

ध्यान दें कि आप विलय दृष्टिकोण का उपयोग करके कुछ समय बचा सकते हैं क्योंकि ए को क्रमबद्ध करने की आवश्यकता नहीं है, बस बी को सॉर्ट करने की आवश्यकता है।