5
द्वारा कार्यान्वित प्राथमिकता कतार पर डिजस्ट्रा के एल्गोरिदम के लिए चलने का समय तो मुझे यह जानकर उत्सुकता है कि एल्गोरिदम के लिए चलने वाला समय एक क्रमबद्ध सूची/सरणी द्वारा लागू प्राथमिकता कतार पर चल रहा है। मुझे एक अपरिवर्तित सूची/सरणी के लिए पता है यह ओ ((एन^2 + एम) है) जहां एन शिखर की संख्या है और किनारों की संख्या एम है। इस प्रकार यह ओ (एन^2) समय के बराबर है। लेकिन अगर मैं एक क्रमबद्ध सूची/सरणी का उपयोग करता तो यह तेज़ होगा ... चलने का समय क्या होगा? मुझे पता है कि extractmin निरंतर समय होगा।
एक साथ सभी क्रमबद्ध समीपता सूचियों विलय:क्रमबद्ध सूची/सरणी