समय जटिलता

Question

के लिए एल्गोरिदम का विश्लेषण मैं एक एल्गोरिदम का विश्लेषण कर रहा हूं और मैं सिर्फ यह जानना चाहता हूं कि मैं सही रास्ते पर हूं या नहीं।

इस एल्गोरिदम के लिए, मैं केवल उस रेखा पर गुणाओं की गिनती कर रहा हूं जिसमें *** है।

यहाँ एल्गोरिथ्म है:

1. तो मैं सबसे भीतरी लाइन से शुरू कर रहा हूँ, मैं वहाँ 2 परिचालन (दो गुणा) देखते हैं देख सकते हैं।
2. अब मैं 2 आंतरिक अधिकांश लूप देख रहा हूं, इसलिए मैं बता सकता हूं कि p=p*20*z बिल्कुल (j) + (j-1)+(j-2)+(j-3)...1 बार निष्पादित हो जाता है। यह j(j+1)/2 के बराबर होता है।
3. तो कुल मिलाकर, क्योंकि दो गुणा हैं, यह 2 * (j(j+1)/2) होता है।
4. अंत में, "i" लूप बिल्कुल n बार होता है, इसलिए, कुल मिलाकर, यह n(2 * (n(n+1)/2)) है।

यह मेरे पीछे मेरी विचार प्रक्रिया है। क्या मैं सही हूँ? धन्यवाद।

Answer 1

आपकी विचार प्रक्रिया सही है। आपको जे टर्म को एन के साथ प्रतिस्थापित करने की आवश्यकता है (एन सबसे बड़ा मूल्य जे मान सकता है), लेकिन शायद यह एक टाइपो है।

इसके अलावा, आप जहाँ आप कर रहे हैं से आगे सरल कर सकते हैं:

n(2*(n(n+1)/2)) 
2*n*(n^2+n)/2 
n^3+n^2 

=> O(n^3) 

अंतिम चरण है क्योंकि एन घन अवधि एक बहुत बड़ा दर की तुलना में एन अवधि हम कह सकते हैं यह हावी होगा चुकता से बढ़ेगा बड़े एन के लिए रनटाइम। केवल एक अन्य बिंदु का उल्लेख यह है कि आपको शायद स्टोर को पी को एक ऑपरेशन के साथ-साथ दो गुणा के रूप में माना जाना चाहिए, हालांकि स्पष्ट रूप से यह सरलीकृत बड़े-ओ रनटाइम को नहीं बदलेगा।

1. i <= n
2. j <= n
3. k <= j

असल:

Answer 2

इस विशिष्ट उदाहरण में संगणना अगर आपको लगता है कि सभी तीन छोरों ही बाहर निकलें हालत up to n है पता कर सकते हैं सरल किया जा सकता है तीसरा पाश n पुनरावृत्तियों को भी चलाएगा क्योंकि j <= n तो k <= n, इसका मतलब यह है कि जटिलता n * n * n = O(n^3)

Answer 3

होगा इस तरह आप विधिपूर्वक अपने एल्गोरिथ्म के विकास के क्रम में प्राप्त कर सकते हैं: