7
बेवकूफ सवाल के लिए खेद है। मैं अपनी याददाश्त को जॉग नहीं कर सकता और गुगलिंग ने मुझे इस सवाल का जवाब देने में मदद नहीं की।, ओ (| ई | * | वी |) जटिलता बहुपद माना जाता है या नहीं?
इसलिए मूल रूप से ग्राफ जी (वी, ई) दिया गया, मुझे पता है कि ओ (| वी |^2) या ओ (| ई |^2 + | वी |^2) बहुपद जटिलता माना जाता है, इसलिए ओ (| ई | * | वी |) बहुपद है? यदि नहीं, तो यह किस तरह की जटिलता है? मेरा मानना है कि यह छद्म-बहुपद नहीं है।
एक और सवाल यह है: क्या ओ (एम * एन) बहुपद माना जाता है, दिया गया एम और एन किसी समस्या के लिए दो स्वतंत्र इनपुट के आकार हैं? मैं यहां पर बहुपद समय की अवधारणा को स्पष्ट करना चाहता हूं और जानना चाहता हूं कि ओ (एम * एन) के पास इसकी जटिलता के लिए एक अलग नाम है या नहीं।
ओह, हाँ। मुझे बूओ :), मैं उसे कैसे देख सकता हूं? एक और सवाल यह है: क्या ओ (एम * एन) बहुपद है, एम और एन किसी समस्या के दो इनपुट के आकार हैं? मैं बस यहां बहुपद समय की अवधारणा को स्पष्ट करना चाहता हूं। – Simo
@ सिमो, मैं आपके अनुवर्ती प्रश्न को समझ नहीं पा रहा हूं। यदि आपको इसके विपरीत छद्म-बहुपद के उदाहरणों की आवश्यकता है, तो यहां देखें: http://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial –
अंतर यह है कि छद्म-बहुपद जटिलता यह मामला क्षमता (यानी, सही हाथ का आकार) पर निर्भर करता है और यह मान धोखाधड़ी से बड़ा हो सकता है। –