में हे (एन) एक सरणी में सभी मतभेदों को

Question

प्रश्न खोजें: एक क्रमबद्ध सरणी एक ए से तत्वों के सभी संभव अंतर मिल को देखते हुए

मेरे समाधान:

for (int i=0; i<n-1; ++i) { 
    for (int j=i+1; j<n; ++j) { 
    System.out.println(Math.abs(ai-aj)); 
    } 
} 

ज़रूर, यह हे है (एन^2), लेकिन मैं चीजों को गिनती नहीं करता हूं। मैंने ऑनलाइन देखा और मुझे यह मिला: http://www.careercup.com/question?id=9111881। यह कहता है कि आप बेहतर नहीं कर सकते हैं, लेकिन एक साक्षात्कार में मुझे बताया गया था कि आप ओ (एन) कर सकते हैं। कौन सा सही है?

Answer 1

पहला विचार यह है कि आप इस तथ्य का उपयोग नहीं कर रहे हैं कि सरणी क्रमबद्ध है। आइए मान लें कि यह बढ़ते क्रम में है (कमी को समान रूप से संभाला जा सकता है)।

हम यह भी सच है कि मतभेदों को दूरबीन (i> जे) का उपयोग कर सकते हैं:

a_i - a_j = (a_i - a_(i-1)) + (a_(i-1) - a_(i-2)) + ... + (a_(j+1) - a_j) 

अब, एक नया अनुक्रम का निर्माण यह है कहते हैं, कि, सरल अंतर है (a_i - a_(i-1)) अर्थ। यह करने के लिए केवल एक पास (O(n)) लगता है, और आप दोहराए जाने पर भी छोड़ सकते हैं, जिसका मतलब है a_i छोड़ें।

a_i-a_ji>js_i + s_(i+1) + ... + s_(j+1) के रूप में सभी संभावित अंतर a_i-a_j हैं। तो हो सकता है कि अगर आप उन्हें पाते हुए मानते हैं, तो आपने इसे O(n) समय में किया था। उन्हें मुद्रित करने के लिए, हालांकि, n(n-1)/2 कॉल ले सकते हैं, और यह निश्चित रूप से O(n^2) है।

Answer 2

उदाहरण के लिए तत्वों साथ एक सरणी के लिए {2 , 2 , ..., 2 ⁿ} वहाँ n ⋅ (n-1)/2 संभव मतभेद हैं, और उनमें से कोई भी बराबर नहीं है। तो ओ (एन) मतभेद हैं।

के बाद से आप उन सभी की गणना करने में है, तो आप भी कम से कम O (n) समय की जरूरत है।

Answer 3

हल या अवर्गीकृत कोई फर्क नहीं पड़ता, आप प्रत्येक अंतर भी कम समय में यह तो ऐसा करने के लिए कोई रास्ता नहीं है की गणना करने के लिए है अगर n^2,

प्रश्न गलत पूछा गया था, या तो आप सिर्फ ओ कर (एन) और उसके बाद 42 अन्य एन बार प्रिंट करें: डी

Answer 4

आप सरणी सामग्री को सॉर्ट करने से पहले यादृच्छिक पूर्णांक मानते हुए एक और काउंटर-उदाहरण प्राप्त कर सकते हैं। फिर मौका कि दो मतभेद, ऐ-अज बनाम अक - अल, या यहां तक ​​कि ऐ-अज बनाम अज-अक, वही हैं जो केवल ओ (एन) अलग मतभेद एआई-अज होने के लिए बहुत छोटे हैं।

यह देखते हुए कि, आपके साक्षात्कारकर्ता का प्रश्न उन विशेष परिस्थितियों को समझाना है जो ओ (एन) समाधान की अनुमति देते हैं। एक संभावना यह है कि सरणी मान सभी संख्या 0 0n में हैं, क्योंकि इस मामले में अधिकतम पूर्ण अंतर केवल n है।

मैं ओ (एन एलजी एन) में ऐसा कर सकता हूं लेकिन ओ (एन) नहीं। तत्व n + 1 के सरणी द्वारा सरणी सामग्री का प्रतिनिधित्व तत्व के साथ 1 पर सेट किया गया है जहां सरणी में कोई मान है I फिर सरणी को स्वयं के साथ घूमने के लिए एफएफटी का उपयोग करें - एक अंतर Ai - Aj = k है जहां संकल्प का kth तत्व शून्य है।

Answer 5

यदि साक्षात्कारकर्ता सैद्धांतिक खेलों का शौक है, तो शायद वह इनपुट और परिणामों की एक तालिका का उपयोग करने के बारे में सोच रहा था? किसी भी इनपुट के आकार पर एक सीमा के साथ समस्या, और यह एक ज्ञात समाधान है, तालिका लुकअप द्वारा हल किया जा सकता है। यह देखते हुए कि आपने पहली बार उस तालिका को बनाया और संग्रहीत किया है, जो बड़ा हो सकता है।

तो अगर सरणी का आकार सीमित है, तो समस्या को तालिका लुकअप द्वारा हल किया जा सकता है, जो (कुछ मान्यताओं को देखते हुए) निरंतर समय में भी किया जा सकता है। अनुमोदित, के अधिकतम सरणी आकार के लिए भी दो (32-बिट पूर्णांक मानते हुए) तालिका सामान्य कंप्यूटर की स्मृति या डिस्क पर फिट नहीं होगी। सरणी के बड़े अधिकतम आकार के लिए, आप "ज्ञात ब्रह्मांड में फिट नहीं होंगे" आकार में हैं। लेकिन, सैद्धांतिक रूप से, यह किया जा सकता है।

(लेकिन वास्तविकता में, मुझे लगता है कि जेन्स Gustedt की टिप्पणी अधिक होने की संभावना है।)