प्राइम का एल्गोरिदम समय जटिलता

Question

मैं प्राइम के एल्गोरिदम के लिए Wikipedia entry पर देख रहा था और मैंने देखा कि आसन्नता मैट्रिक्स के साथ इसकी समय जटिलता ओ (वी^2) है और इसकी समय जटिलता एक ढेर और आसन्नता सूची के साथ ओ (ई एलजी (वी)) जहां ई किनारों की संख्या है और वी ग्राफ में शिखर की संख्या है।

चूंकि प्राइम के एल्गोरिदम का उपयोग घनत्व ग्राफ में किया जाता है, ई V^2 तक पहुंच सकता है, लेकिन जब ऐसा होता है, तो ढेर के साथ समय जटिलता ओ (वी^2 एलजी (वी)) बन जाती है जो ओ (वी^2)। जाहिर है, एक ढेर सिर्फ सरणी को खोजने पर प्रदर्शन में सुधार करेगा, लेकिन समय जटिलता अन्यथा कहती है।

एल्गोरिदम वास्तव में सुधार के साथ कैसे धीमा हो जाता है?

Answer 1

भले ही ढेर आपको सरणी के माध्यम से खोजने से बचाता है, फिर भी यह एल्गोरिदम के "अद्यतन" भाग को धीमा कर देता है: सरणी अद्यतन ओ (1) हैं, जबकि हेप अपडेट ओ (लॉग (एन)) हैं।

संक्षेप में, आप एल्गोरिदम के एक हिस्से में दूसरी गति में गति की गति करते हैं।

कोई फर्क नहीं पड़ता कि आपको एन बार खोजना होगा। हालांकि, घने ग्राफ में, आपको बहुत (~ V^2) अपडेट करना होगा, और स्पैस ग्राफ में, आप नहीं करते हैं।

मेरे सिर के शीर्ष से एक और उदाहरण एक सरणी में तत्वों की खोज कर रहा है। यदि आप केवल एक बार ऐसा कर रहे हैं, तो रैखिक खोज सबसे अच्छी है - लेकिन यदि आप बहुत सारे प्रश्न पूछते हैं, तो इसे सॉर्ट करना बेहतर है और हर बार बाइनरी खोज का उपयोग करना बेहतर होता है।

Answer 2

मुझे लगता है कि आप इसे कुछ डिग्री के लिए गलत पढ़ते हैं। घने ग्राफ के लिए, लेख समय जटिलता ओ (ई + वी लॉग वी) के साथ फाइबोनैकी ढेर का उपयोग करने के बारे में बात करता है, जो काफी बेहतर है।

Answer 3

एल्गोरिथम का परिचय (कारमेन) से

समय = Θ (वी) · टी (EXTRACT मिनट) + Θ (ई) · टी (DECREASE-कुंजी)

 
        T(EXTRACT-MIN) T(DECREASE-KEY) Total 

1. array   O(V)    O(1)    O(V^2) 
2. binary heap  O(lgV)   O(lgV)   O(E lgV) 
3. Fibonacci heap O(lgV)   O(1)    O(E + VlgV) 

विभिन्न डेटा संरचनाओं का उपयोग विभिन्न समय जटिलताओं का कारण बनता है।