एक सरणी सूची

Question

के माध्यम से पुनरावृत्त करने के लिए समय जटिलता मेरे पास एक सरणी सूची है जिसे मैं फिर से चलाता हूं। प्रत्येक यात्रा में मैं get() फोन एक तत्व प्राप्त करने के लिए, और अगर है कि आइटम कुछ हालत गुजरता है, यह add()

List<Item> items = new ArrayList<Item>(); 
List<Item> lessItems = new ArrayList<Item>(); 
for(int index = 0; index < items.size(); index++){ 
    Item toCheck = items.get(i); 
    if(toCheck meets some condition){ 
     lessItems.add(toCheck); 
    } 
} 

का उपयोग कर एक नई सरणी सूची में जोड़ा जाता मुझे यकीन है कि क्या समय जटिलता यहाँ है नहीं कर रहा हूँ। मैं सभी वस्तुओं पर() प्राप्त कर रहा हूं ताकि ओ (एन) हो। फिर मैं संभावित रूप से सभी वस्तुओं पर add() को भी कॉल कर रहा हूं, इसलिए एक और ओ (एन) है। इस पर भी यकीन नहीं है।

Answer 1

बिग-ओ और इसी तरह के नोटेशन समय जटिलता पर असीमित सीमाएं हैं। उन्होंने संख्यात्मक गुणांक को त्याग दिया और इनपुट के आकार के कार्य के रूप में रन-टाइम का अनुमान लगाने के लिए उपयोग किया जाता है।

तो, 2*n, 3*n, आदि। O(n), और 2*nlog(n), 3*nlog(n), आदि के रूप में दर्शाए जाते हैं। O(nlog(n)) के रूप में दर्शाए जाते हैं।

चूंकि ऐड() आपरेशन इस मामले में केवल एक ही तत्व सम्मिलित करता है, अपने क्रम लगभग, (some small constant)k*1, (some constant)j*(n+some constant(k)) के रूप में कुल रनटाइम दे रही है दूसरे शब्दों j*n, या O(n) में है,।

इस मामले और ऐसे सभी इसी तरह के मामलों में, किसी भी निरंतर कश्मीर द्वारा n गुणा क्रम अर्थ O(n) के रूप में प्रतिनिधित्व किया जाएगा इनपुट ArrayList के आकार के साथ रैखिक भिन्न होता है।

Answer 2

अन्य सभी उत्तरों गलत यहां हैं।

1. items सूची पुनरावृत्ति के लिए आपका पहला पाश: जटिलता सूची lessItems के अंत तक O(n)
2. सम्मिलित प्रत्येक आइटम है: के रूप में अन्य लोगों ने कहा सामान्य सरणी में यह O(n) हो जाएगा। लेकिन जावा amortized array का उपयोग कर ArrayList के लिए लागू करता है। इसका मतलब है कि सरणी के अंत में डालने पर, एल्गोरिदम केवल Amortized O(1) खर्च करता है। या आप कह सकते हैं O(1)

इसलिए आपके कोड की जटिलता है: O(n) * amortized O(1)।

dynamic array

अतिरिक्त नोट 1: संक्षेप में O(n)

एक अन्य संदर्भ है

तो सरणी के अंत में डालने की जटिलता, O(N) है तो कुल जटिलता O(N^2) है, नहीं ओ (2 * एन) के रूप में अन्य उत्तरों ने कहा। क्योंकि डालने के लिए कुल जटिलता होगा: 1 + 2 + 3 + ...+ n = n*(n+1)/2

addtional नोट 2:

official document के रूप में कहता है:

आकार, isEmpty, मिलता है, सेट, इटरेटर, और listIterator संचालन चलाने निरंतर समय में।ऐड ऑपरेशन अमूर्त स्थिर समय, में चलता है, जिसमें एन तत्वों को जोड़ने के लिए ओ (एन) समय की आवश्यकता होती है। अन्य सभी संचालन रैखिक समय में चलते हैं (मोटे तौर पर बोलते हैं)। लगातार कारक लिंकडलिस्ट कार्यान्वयन के लिए इसकी तुलना में कम है।

अतिरिक्त नोट 3:

private void ensureExplicitCapacity(int minCapacity) { 
     modCount++; 

     // overflow-conscious code 
     if (minCapacity - elementData.length > 0) 
      grow(minCapacity); 
    } 

private void grow(int minCapacity) { 
     // overflow-conscious code 
     int oldCapacity = elementData.length; 
     int newCapacity = oldCapacity + (oldCapacity >> 1); 
     if (newCapacity - minCapacity < 0) 
      newCapacity = minCapacity; 
     if (newCapacity - MAX_ARRAY_SIZE > 0) 
      newCapacity = hugeCapacity(minCapacity); 
     // minCapacity is usually close to size, so this is a win: 
     elementData = Arrays.copyOf(elementData, newCapacity); 
    } 

स्रोत कोड के रूप में, ने कहा है कि जब प्रोग्राम जोड़ें:

यहाँ grow विधि का तर्क है कि मैं आधिकारिक जावा स्रोत कोड से ले लिया है है तत्व जो मौजूदा क्षमता की तुलना में सरणी का आकार बड़ा बनाता है, ऐरे उगाया जाएगा। वयस्क सरणी के नए आकार होगा:

int newCapacity = oldCapacity + (oldCapacity >> 1); 

यह एक चाल है कि डालने amortized O(1)

Answer 3

आप एक यात्रा कर रहे हैं बनाने के है, और कहा कि हे (एन) की है।

तुम भी एक ArrayList हे की है जो करने के लिए आइटम जोड़ रहे हैं (1) (Amortized)

एक सूचकांक हो रही भी हे है (1)।

तो अपने कर रही हे (एन) बार, हे के संचालन (1), जिनमें से हे (एन) होने जा रहा है।