6
मेरे पास एक अप्रत्यक्ष असीमित ग्राफ जी = (वी, ई) और इसके शिखर के यादृच्छिक रूप से चुने गए सबसेट एस हैं। मैं यह जांचना चाहता हूं कि एस में शिखर पारस्परिक रूप से आसन्न हैं (यानी एक पूर्ण उपग्राफ/एक क्लिक्स बनाएं)।
मैं निम्नलिखित एल्गोरिथ्म (छद्म कोड) है:एक प्रेरित सबग्राफ पूरा होने पर यह पता लगाने के लिए फास्ट एल्गोरिदम
foreach vertex in S {
// Check that the vertex has enough edges
if (vertex.edges.count < S.size - 1)
return false;
// Check that there is an edge to each vertex in S
foreach vertex2 in S {
if (!vertex.hasEdgeTo(vertex2))
return false;
}
}
return true;
समस्या यह है कि इस एल्गोरिथ्म के बुरी से बुरी हालत प्रदर्शन हे है (| वी |) (मामले में सबसेट एस सभी शामिल हैं जब एक पूर्ण ग्राफ के शिखर)।
मेरा प्रश्न है: क्या एक तेज एल्गोरिदम है जो एक बेहतर बड़ी ओ सबसे बुरी स्थिति जटिलता के साथ चलता है?
क्या आपका मतलब _O (| वी | ²) _ नहीं है? – Svante
आप केवल एक बार प्रत्येक किनारे की जांच करके निरंतर कारक को रोक सकते हैं। इसके लिए, आंतरिक लूप केवल उन सभी शीर्षकों के माध्यम से चलना चाहिए जो अभी तक बाहरी में नहीं हैं। यह निश्चित रूप से बेहतर _O_ जटिलता नहीं देता है। – Svante
हां, ओ (| ई |^2) के बजाय ओ (| वी |^2) है, इसे ठीक किया गया है। मुझे पता है कि मैं आधा समय कर सकता हूं, स्पष्टता के लिए छोड़ दिया। आपकी टिप्पणियों के लिए आभार। –