क्या मैं सोच रहा हूं कि यह स्निपेट ओ (एन^3) है?

Question

collection.Where(i => i.condition) 
.ToList() 
.ForEach(i => SomeComplicatedOpInvolving_i); 

मैं जवाब देने की कोशिश नहीं कर रहा हूं कि ऐसा करने का एक आसान तरीका है, बस इसे एक प्रयोग प्रयोग के रूप में देखें।

सबसे पहले, क्या मैं सोच रहा हूं कि यह तीन लूप है? Where(), ToList() और ForEach()?
सबसे दूसरा, (मान लीजिए कि यह तीन लूप है) क्या मैं सोच रहा हूं कि यह बड़ी ओ नोटेशन में 3 की शक्ति के लिए है?

सभी को धन्यवाद।

Answer 1

नहीं, असल में। मुझे लगता है कि यह ओ (एन) होना चाहिए। हे में

Where() रन (एन) के रूप में अच्छी तरह से (यह मानते हुए condition स्थिर है) Where के सभी परिणामों पर

ToList() रन, इसलिए हे (एन) द्वारा उत्पादित पूरी सूची पर बहुत

ForEach() रन ToList एक बार, तो ओ (एन) भी। मुझे लगता है SomeComplicatedOpInvolving_i मैं के की संख्या के साथ पैमाने पर नहीं है ...

कुंजी यहां मुद्दा यह है कि छोरों नहीं लगाए गए हैं, वे एक के बाद एक को चलाने - तो कुल रनटाइम 3 * हे (एन) है, जो ओ (एन) के समान है।

Answer 2

नहीं, वे घोंसला वाले लूप नहीं हैं। यह चालू है)।

ToList() का उपयोग करने से बचें, जिसके लिए ओ (एन) भंडारण का कोई अच्छा कारण नहीं है। यह blog post देखें।

Answer 3

नहीं, यह O(n) है। यदि लूप के भीतर लूप के अंदर लूप था तो यह केवल O(n^3) होगा।

Answer 4

यह O(n) है।

Where के रूप में इसका मतलब है कि Where की लागत लगभग A x n है, कुछ A के लिए O(n) है।

इसी ToList और ForEach के रूप में भी O(n) जिसका अर्थ है उनकी लागत लगभग B x n और C x n संबंधित कुछ B और कुछ C के लिए है।

इसका मतलब है कि कुल लागत लगभग है:

(A x n) + (B x n) + (C x n) 
= (A + B + C) x n 
= D x n 

कुछ D के लिए (हम वास्तव में कभी नहीं परवाह क्या A, B और C थे, इसलिए हम भी परवाह नहीं है क्या A + B + C है, इसलिए सिर्फ फोन हमारे समीकरण को सरल बनाने के लिए D)।

इसलिए यह ऑपरेशन O(n) है।

Answer 5

collection.Where(i => i.condition) // is O(n) where n is the size of collection 
.ToList() // is O(m) where m is the number if items with i.condition true 
.ForEach(i => SomeComplicatedOpInvolving_i); // O(m) where m is the number if items with i.condition true 

मानते हैं कि कुछ कॉम्प्लेक्टेड ओपइन्वॉलिंग ओ (1) है, उदा। यदि आपके पास अधिक आइटम हैं तो यह अधिक समय नहीं बनाता है।

यह देखते हुए कि

when m is never bigger then n, then 
O(n) + O(m) + O(m) == O(n) 

फिर टुकड़ा (एन)

Answer 6

यह हे है हे है (collection.Size) * ओ (SomeComplicatedOpInvolving_i)।