मैं समय जटिलता सीखना शुरू कर रहा हूं, और मैंने कुछ सरल प्रकार के लिए जटिलता के उदाहरणों को देखा।गहराई की पहली जटिलता-प्रथम ग्राफ एल्गोरिदम
मैं जानना चाहता था कि |V|=n और |E|=m के साथ ग्राफ में गहराई से पहली खोज के लिए हम औसत समय जटिलता की गणना कैसे करते हैं, प्रारंभ नोड 'यू' और अंत नोड 'v' होने दें।
डीएफएस के लिए समय जटिलता ओ (एन + एम) है। हम इस जटिलता को इस तथ्य पर विचार करते हैं कि हम केवल एक बार प्रत्येक नोड पर जा रहे हैं और पेड़ के मामले में (कोई चक्र नहीं) हम एक बार सभी किनारों को पार कर रहे हैं।
उदाहरण के लिए, यदि प्रारंभ नोड आप है, और अंत नोड v है, तो हम सबसे बुरी स्थिति परिदृश्य पर सोच रहे हैं जब वी अंतिम बार देखा जाएगा। तो हम आपके पहले पड़ोसी के पहले घटक, फिर दूसरे पड़ोसी के जुड़े घटक, और आखिरी पड़ोसी के कनेक्टेड घटक तक, जहां हम पाते हैं, तक हम यात्रा शुरू कर रहे हैं। हमने प्रत्येक नोड का केवल एक बार दौरा किया है, और नहीं एक ही किनारे को एक से अधिक बार पार किया।
सम्मानित सर, मैं जटिलता विश्लेषण के लिए नया हूं, असल में मैं ओएस पर एक प्रोजेक्ट कर रहा हूं, मैं संसाधन आवंटन ग्राफ में चक्र ढूंढने की कोशिश कर रहा हूं ... मैं हूं पहली बार गहराई के संशोधन का उपयोग करके चक्र ढूंढना .. मैं बैंकर के एल्गोरिदम के साथ इस एल्गोरिदम की जटिलता की तुलना करने की कोशिश कर रहा हूं .. क्या आप "औसत औसत प्रदर्शन" के गणितीय व्युत्पन्न को दे सकते हैं – Learner
"औसत केस प्रदर्शन" अपेक्षित मूल्य है (जो है संभाव्यता सिद्धांत से एक शब्द) इनपुट के कुछ अनुमानित संभाव्यता वितरण पर चलने वाले समय के। –
यह हे हो जाएगा (n + m) यदि ग्राफ समीपता सूची लेकिन के रूप में दिया जाता है, तो ग्राफ निकटता मैट्रिक्स के रूप में है तो जटिलता हे है (एन * एन), हम के रूप में जब तक हम किनारे नहीं पाते हैं तब तक पूरी पंक्ति से गुज़रना पड़ता है।
मुझे पता है कि यह बहुत देर हो चुकी है .. लेकिन अन्य जो लोग खोज रहे हैं, उनके लिए एक विस्तृत विश्लेषण है। http://techieme.in/depth-first-traversal – dharam