फ़ंक्शन की समय जटिलता

Question

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

पहले समारोह जाता है:

r = 0 
# Assignment is constant time. Executed once. O(1) 
for i in range(n): 
    for j in range(i+1,n): 
     for k in range(i,j): 
      r += 1 
      # Assignment and access are O(1). Executed n^3 

इस तरह।

मुझे लगता है कि यह ट्रिपल नेस्टेड लूप है, इसलिए यह ओ (एन^3) होना चाहिए। लेकिन मुझे लगता है कि यहां मेरा तर्क बहुत कमजोर है। मैं वास्तव में नहीं मिलता है क्या यहाँ

दूसरा समारोह ट्रिपल नेस्टेड लूप के अंदर चल रहा है है:

i = n 
# Assignment is constant time. Executed once. O(1) 
while i>0: 
    k = 2 + 2 
    i = i // 2 
    # i is reduced by the equation above per iteration. 
    # so the assignment and access which are O(1) is executed 
    # log n times ?? 

मैं इस एल्गोरिथ्म पता चला हे होने के लिए (1)। लेकिन पहले फंक्शन की तरह, मुझे नहीं लगता कि समय-लूप में क्या चल रहा है।

क्या कोई फ़ंक्शंस की समय जटिलता के बारे में अच्छी तरह से समझा सकता है? धन्यवाद!

Answer 1

सबसे पहले, पहले कार्य के लिए, समय जटिलता ओ (एन लॉग एन) के करीब प्रतीत होती है क्योंकि प्रत्येक लूप के पैरामीटर हर बार घटते हैं।

इसके अलावा, दूसरे फ़ंक्शन के लिए, रनटाइम ओ (लॉग 2 एन) है। सिवाय, कहो मैं == एन == 2. एक रन के बाद मैं 1 है। एक के बाद मैं 0.5 है। एक और के बाद मैं 0.25 है। और इतने पर ... मुझे लगता है कि आप int (i) चाहते हैं।

प्रत्येक समारोह के लिए एक कठोर गणितीय दृष्टिकोण के लिए, आप https://www.coursera.org/course/algo पर जा सकते हैं। यह इस तरह की चीज के लिए एक अच्छा कोर्स है। मैं अपनी गणना में मैला था।

Answer 2

इस तरह के एक सरल मामले के लिए, आप कर सकते थे find the number of iterations of the innermost loop as a function of n exactly:

sum_(i=0)^(n-1)(sum_(j=i+1)^(n-1)(sum_(k=i)^(j-1) 1)) = 1/6 n (n^2-1) 

अर्थात, Θ(n**3) समय जटिलता (see Big Theta): यह मानता है कि r += 1 हे है (1) यदि rO(log n) अंक (model has words with log n bits)।

दूसरा पाश भी आसान है: i //= 2i >>= 1 है। nΘ(log n) अंक होते हैं और प्रत्येक यात्रा एक बाइनरी अंक (सही शिफ्ट) चला जाता है और इसलिए पूरे पाश Θ(log n) समय जटिलता है अगर हम मानते हैं कि log(n) अंकों की i >> 1 पारी हे है (1) आपरेशन (एक ही मॉडल पहले उदाहरण के रूप में)।