YouTube

Got a YouTube account?

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

Hindi subtitles

← 05-21 Using Heaps

Get Embed Code
3 Languages

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

  1. मैं यह पहले का वर्णन किया गया के रूप में, प्रत्येक नोड के लिए हम इस परीक्षण के लिए दूरी कम से कम अभी तक पता करते हैं।
  2. है कि एक ढेर ऑपरेशन - n बातों के ढेर में है, तो यह एक logn ऑपरेशन है।
  3. तो यह पूरी तरह एक बार प्रत्येक नोड के लिए - भाग लेने के लिए जा रहा है तो यह एल्गोरिथ्म का हिस्सा
  4. वास्तव में समय और logn लेता है।
  5. किनारों के ग्राफ में से प्रत्येक के लिए, हम यह दूरी कम करने कार्रवाई करते हैं,
  6. जो भी एक logn समय ऑपरेशन - है इसलिए कि एक logn या mlogn के लिए प्रत्येक किनारे हो जाता है।
  7. अब, इन दोनों को किया हो तो हम वास्तव में ये एक साथ nlogn और mlogn को जोड़ने के लिए है,
  8. और इस धारणा में कि ग्राफ से जुड़ा है, इस एम इस एन - के रूप में कम से कम में बड़ा हो गया है
  9. क्योंकि यह शब्द हावी - तो कि हमें मैं (mlogn) के समय से चल रहा एक कुल देता है।
  10. मैं एक अलग रूप में, बस उल्लेख करेंगे वहाँ हो गया है कि कुछ बहुत चालाक डेटा संरचना काम किया
  11. Fredman और Tarjan, के रूप में एक ही Tarjan से पहले, कि यह वास्तव में कमी होना करने के लिए अनुमति देता है
  12. समय चल रहा nlogn + m बनने के लिए अनुमति देता है ढेर के एक बहुत ही विशेष प्रकार का उपयोग कर।
  13. पर कम से कम m बस सभी किनारों पर जाएँ हमें। तो यह एक बहुत उल्लेखनीय परिणाम है।
  14. मैं यह अतीत में क्रियान्वित किया है। यह मेरे लिए इतनी तेजी से चला नहीं था।
  15. ये asymptotic परिणाम कर रहे हैं में है कि भूमि के ऊपर रखने के इस फैंसी ढेर में लिखें
  16. से - अच्छी तरह से अधिक संरचना अद्यतन किया गया था, मैं तो यह पर्याप्त सक्षम था इसे लागू करने में सक्षम नहीं था।
  17. लेकिन जो हम भूमि के ऊपर के बारे में बात कर रहे थे ढेर बहुत कच्चा है
  18. और हम इस तरह का समय चल रहा हो, elapse बहुत कुशल होना चाहिए।