सूची की एसिम्प्टोटिक जटिलता क्या है। जोड़ें?

Question

मुझे पता चला है कि List.Add() की एसिम्प्टोटिक जटिलता के बारे में बहुत सारे विवाद हैं। इसका स्रोत मुझे संदेह है कि सबसे खराब स्थिति परिदृश्य that causes underlying array to resize है और तर्कसंगत रूप से O(n) ऑपरेशन होगा। हालांकि, array grows twice in size प्रत्येक बार सूची अंतरिक्ष से बाहर हो जाती है। इससे n तत्वों के लिए आवश्यक आकारों की संख्या log(n) के समान होती है।

क्या इसका मतलब यह नहीं है कि Add औसत केस में ऑपरेशन O(n/log(n)) होगा?

List.Add() के लिए वास्तविक बेंचमार्क नीचे है। हालांकि, ऐसे ऑपरेशन के लिए बेंचमार्क वास्तव में अभिव्यक्तिपूर्ण नहीं हैं - हम सीधे (किसी भी विचलन पैमाने पर) रेखा से किसी भी विचलन से पहले स्मृति से बाहर हो रहे हैं।

Answer 1

इसका मतलब है कि List.Add() की amortized complexity आकार बदलने संचालन संक्षेप और उसके बाद कुल सूची में किए गए अतिरिक्त की संख्या से गुणा किया जा सकता है।

T(n) = (2 + 4 + 8 + ... + n/2 + n)/n 

लेकिन ध्यान दें कि योग एक geometric series है, और हम यह सोचते हैं कि यह (योग) n*log(n) की तुलना में बेहतर कर सकते हैं:

T(n) < 2n/n = 2 -> T(n) is in O(1) 

---

नोट: यहाँ मैं आप जोड़कर रूप add() मतलब यह सोचते हैं हूँ । मनमाने ढंग से स्थान में एक तत्व डालने से O(n) समय लगता है, और आपको इसके लिए भी खाता लेना होगा, जो O(1) अमूर्त जटिलता से O(n) अमूर्त जटिलता के अंतिम परिणाम को बदल देगा।