5
पूर्णांकों की एक सरणी को देखते हुए, एक तरीका है जिसके सभी अद्वितीय जोड़े जो 100मेरे कोड की बिग-ओ जटिलता क्या है?
उदाहरण डेटा को जोड़ देता है लिखें:
sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]]
मैं इस सप्ताह के अंत में इस समस्या को हल करने गया था और मेरे समाधान स्केलेबल लगता है, जबकि और कुशल, मैं यह निर्धारित करना चाहता था कि मेरे समाधान का सबसे खराब मामला जटिलता क्या है?
यहाँ मेरी समाधान है:
def solution(arr)
res = []
h = Hash.new
# this seems to be O(N)
arr.each do |elem|
h[elem] = true
end
# how do I determine what Time complexity of this could be?
arr.each do |elem|
if h[100-elem]
h[100-elem] = false
h[elem] = false
res << [elem, 100-elem]
end
end
res
end
दोनों छोरों हे (एन) प्रत्येक कर रहे हैं, और मैं उन्हें जोड़ने के ऊपर: हे (एन + N), इस ओ (2N) के बराबर होता है और 2 लेने एक स्थिर होने के लिए, क्या मैं अपना समाधान मान सकता हूं ओ (एन) है?
यह सही होगा। – screenmutt
मुझे लगता है कि आपकी धारणा मूल रूप से सही हैं। यह भी माना जाता है कि तत्व अर्थपूर्ण होने के लिए नकारात्मक (और 100 से अधिक) हो सकते हैं - अन्यथा प्रारंभिक इनपुट को केवल डुप्लिकेट करने से कोई स्केलिंग लागत हो जाती है और सभी चीजों को भरने के बाद अन्य सभी चीज़ों को निश्चित लागत के रूप में माना जा सकता है। 100। तकनीकी रूप से 'एच [elem] = true' 'ओ (1)' नहीं है (जो कि बहुत से लोग मानते हैं) लेकिन' ओ (लॉग (एन)) 'तो आपकी समग्र जटिलता शायद' ओ (नलॉग (एन)) 'सबसे खराब मामला - आप केवल यह देखते हैं कि यदि आप लाखों पूर्णांक के साथ सरणी में पंप हो गए हैं, हालांकि –
@NeilSlater आप गलत हैं। 'h' एक हैश नक्शा है जो खोज रैखिक समय है। [विकी] (http://en.wikipedia.org/wiki/Hash_table) – screenmutt