YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Hindi subtitles

← 03-12 Running Time of Connected Component

Get Embed Code
3 Languages

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. यह इस एल्गोरिथ्म के चल रहे समय का विश्लेषण करने के लिए महत्वपूर्ण है
  2. हम कुछ पता नहीं कैसे कुशल से है यह है।
  3. और फिर से, कि आदिम चरणों की संख्या के ऊपर की गिनती शामिल करने के लिए जा रहा है,
  4. आदिम बयान, समय है कि एल्गोरिथ्म लेता है जब एक समस्या को हल करने।
  5. हम मान लेंगे, जैसा कि पहले, कि एन ग्राफ में नोड्स की संख्या का प्रतिनिधित्व करता है
  6. और एम किनारों की संख्या का प्रतिनिधित्व करता है।
  7. और यह जाता है कि बाहर बुनियादी रणनीति है कि हम के लिए इस एल्गोरिथ्म का उपयोग करें
  8. एक ग्राफ खोज की तरह है।
  9. वहाँ 2 मुख्य जायके भ्रष्टाचार खोज, पहली खोज गहराई और चौड़ाई पहली खोज की है।
  10. इस एक कि हम के बारे में बात कर रहा है गहराई पहले खोज का एक रूप है।
  11. बाद में हम चौड़ाई पहले खोज का एक संस्करण को देखने के लिए जा रहे हैं
  12. जब हम शुरू में कम से कम रास्तों की तलाश।
  13. लेकिन इस विशेष एल्गोरिथ्म पथ की लंबाई के बारे में चिंतित नहीं है,
  14. यह सिर्फ आंकड़ा जो नोड पथ का किसी भी तरह से पहुँचा जा सकता करने के लिए कोशिश कर रहा है।
  15. तो यह एल्गोरिथ्म पर एक नज़र यहाँ ले जा,
  16. चीज़ें है कि हम सही बल्ले से नोट कर सकते हैं में से एक
  17. इस एक, marked(node) की प्रवक्ता है = True,
  18. केवल एक बार ग्राफ में प्रत्येक नोड के लिए निष्पादित किया जा सकता।
  19. तो भले ही यह थोड़ा सा ठीक जब इस पर अमल करने के लिए है बता जा करने के लिए मुश्किल है,
  20. हम हर नोड के रूप में चिह्नित हो जाओ करने के लिए जा रहा है दिन के अंत में पता
  21. और कोई नोड दो बार के रूप में चिह्नित हो जाओ करने के लिए जा रहा है।
  22. तो इसका मतलब कि एक बार ग्राफ में प्रत्येक नोड के लिए हम इस कथन निष्पादित करने के लिए जा रहे हैं
  23. और इस बयान और इस लूप।
  24. और इस लूप क्या होता है?
  25. यह माध्यम से चला जाता है और मूल रूप से सभी किनारों कि इस विशेष नोड (नोड) से बाहर आने का दौरा किया।
  26. और प्रत्येक उन किनारों के लिए, अच्छी तरह से, यह कुछ काम करता है।
  27. यह जाँच करता है या नहीं यह चिह्नित किया है, जो हमें लगता है के लिए जा रहे हैं एक इकाई समय ऑपरेशन, है
  28. किसी तरह का अच्छा हैश तालिका और यह अच्छी तरह से व्यवहार करती है,
  29. और एक आवर्ती कॉल, और हम किसी भी तरह के लिए खाते में है के लिए जा रहे हैं
  30. सब सामान है कि इस रीकर्सिव कॉल में होता है, लेकिन चलो क्षण के लिए उस के बारे में चिंता नहीं।
  31. यह यह एक मुख्य गणना कर रहा है, यह जो कुछ भी यह मूल्य जोड़ने वापस हो जाता है
  32. इस मात्रा करने के लिए यहाँ, तो यह देता है।
  33. तो ये बयान यहाँ एक बार प्रति नोड निष्पादित हो करने के लिए जा रहे हैं।
  34. यह बयान एक बार प्रति नोड निष्पादित हो करने के लिए जा रहा है।
  35. यह बयान एक बार ग्राफ में बढ़त प्रति निष्पादित हो करने के लिए जा रहा है
  36. क्योंकि प्रत्येक नोड के लिए यह उस नोड से उत्पन्न सभी किनारों पर जाएँ करने के लिए जा रहा है।
  37. तो भी यह बहुत क्या का ट्रैक रखने के लिए मुश्किल है, हालांकि जब मार डाला जा रहा है,
  38. हम जानते हैं कि कुल समय चल रहा है यहाँ बड़ी थीटा होने जा रहा है
  39. नोड्स प्लस ग्राफ में किनारों की कुल संख्या की संख्या का।
  40. तो है कि क्या इस रूप में चिह्नित घटक में क्या हो रहा है।
  41. और फिर हो क्या रहा है यहाँ के बाहर, यह के रूप में चिह्नित एक बार सब पर निष्पादित हो जाता है,
  42. ग्राफ में प्रत्येक नोड के लिए तो यह कर सकते हैं या इस कथन का निष्पादन नहीं हो सकता,
  43. जो घटक को चिह्नित करने के लिए कॉल करता है।
  44. तो हम पर सभी नोड्स पुनरावृति करने जा रहे हैं,
  45. और फिर से, हम कुछ काम लेकिन नोड प्रति नहीं से अधिक लगातार काम करने के लिए जा रहे हैं।
  46. और अगर हम हमारे चल रहे समय में यहाँ देखो, यहाँ में एक और एन जोड़ने बड़ा थीटा नहीं बदलता है।
  47. फिर से, यहां तक कि हालांकि यह आंकड़ा जो बाहर जब क्रियान्वित कर रहे हैं के लिए बहुत जटिल है,
  48. n + m का बड़ा थीटा वास्तविक समय चल रहा है।
  49. यह उनका कहना है कि इस ग्राफ के आकार में रैखिक है लायक है।
  50. ग्राफ नोड्स की कुछ संख्या और किनारों की कुछ संख्या होती है,
  51. और कि पूरी कहानी है।
  52. तो यह वास्तव में रेखीय ग्राफ के आकार में है।