जटिलता

Question

आज कक्षा में मेरी शिक्षक ब्लैकबोर्ड पर लिखा है इस पुनरावर्ती भाज्य एल्गोरिथ्म:

int factorial(int n) { 
    if (n == 1) 
     return 1; 
    else 
     return n * factorial(n-1); 
} 

उन्होंने कहा कि T(n-1) + 1 की लागत है।

फिर पुनरावृत्ति विधि के साथ उसने कहा कि T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, इसलिए n - j = 1, j = n - 1 पर एल्गोरिदम बंद हो जाता है।

उसके बाद, उन्होंने को T(n-1) + 1 में प्रतिस्थापित किया, और T(1) + n-1 प्राप्त किया।

वह सीधे कहा कि उस के लिए n-1 = 2 ^{(लॉग n-1)}, तो एल्गोरिथ्म की लागत घातीय है।

मैं वास्तव में पिछले दो चरणों को खो दिया। क्या कोई उन्हें मुझे समझा सकता है?

Answer 1

चलिए इस एल्गोरिदम के विश्लेषण से शुरू करते हैं। हम किए गए कार्यों की कुल राशि के लिए पुनरावृत्ति संबंध लिख सकते हैं। एक आधार के मामले के रूप में, आप आकार n + 1 का एक इनपुट के लिए जब एल्गोरिथ्म आकार 1 के इनपुट पर चलाया जाता है काम की एक इकाई है, तो

टी (1) = 1

करना , आपका एल्गोरिदम कार्य के भीतर काम की एक इकाई करता है, फिर आकार एन के इनपुट पर एक ही फ़ंक्शन को कॉल करता है। इसलिए

टी (n + 1) = टी (एन) + 1

आप पुनरावृत्ति के मामले बाहर का विस्तार हैं, तो आप प्राप्त है कि

• टी (1) = 1
• टी (2) = टी (1) + 1 = 2
• टी (3) = टी (2) + 1 = 3
• टी (4) = टी (3) + 1 = 4
• ...
• टी (एन) = n

सामान्य रूप में

तो इस एल्गोरिथ्म की आवश्यकता होगी n काम की इकाइयों को पूरा करने के (अर्थात टी (एन) = एन)।

अगली बात अपने शिक्षक ने कहा था कि

टी (एन) = n = 2 ^{लॉग n}

यह बयान सच है, क्योंकि 2 ^{लॉग x} = x किसी भी nonzero x के लिए, एक्सपोनेंटिएशन और लॉगरिदम एक-दूसरे के व्यस्त संचालन हैं।

तो सवाल यह है: क्या यह बहुपद समय या घातीय समय है? मैं इसे स्यूडोपोलिनोमियल समय के रूप में वर्गीकृत करूंगा।यदि आप इनपुट x को किसी संख्या के रूप में देखते हैं, तो रनटाइम वास्तव में x में बहुपद है। हालांकि, बहुपद समय औपचारिक रूप से परिभाषित किया गया है कि समस्या में इनपुट निर्दिष्ट करने के लिए उपयोग की जाने वाली बिट्स की संख्या के संबंध में एल्गोरिदम का रनटाइम बहुपद होना चाहिए। यहां, संख्या x को केवल Θ (लॉग x) बिट्स में निर्दिष्ट किया जा सकता है, इसलिए 2 ^{रन x} का रनटाइम तकनीकी रूप से घातीय समय माना जाता है। मैंने इस बारे में this earlier answer में लंबाई के रूप में लिखा, और मैं इसे और अधिक विस्तृत स्पष्टीकरण के लिए देखने की अनुशंसा करता हूं।

आशा है कि इससे मदद मिलती है!