मर्ज सॉर्ट जटिलता की गणना कैसे की जाती है?

2024 लेखक: Lynn Donovan | [email protected]. अंतिम बार संशोधित: 2023-12-15 23:47

2 उत्तर। एक नोड A[L, R] को दो नोड्स में विभाजित करने में R−L+1 समय लगता है और फिर विलय दो बच्चे नोड्स A[L, M] और A[M+1, R] फिर से A[R−L+1] समय लेते हैं। इस प्रकार प्रत्येक नोड के लिए, संचालन की संख्या कलन विधि प्रदर्शन उस नोड के अनुरूप सरणी के आकार के दोगुने के बराबर है।

इसके बारे में, मर्ज सॉर्ट कैसे काम करता है?

यहां बताया गया है कि मर्ज सॉर्ट कैसे डिवाइड-एंड-कॉनकॉर का उपयोग करता है:

1. p और r के बीच में स्थिति की संख्या q ज्ञात करके भाग दें।
2. विभाजन चरण द्वारा बनाई गई दो उप-समस्याओं में से प्रत्येक में उप-सरणियों को पुनरावर्ती रूप से क्रमबद्ध करके जीतें।
3. दो सॉर्ट किए गए सबअरे को वापस सिंगल सॉर्ट किए गए सबअरे ऐरे में मर्ज करके मिलाएं [p..

साथ ही, मर्ज सॉर्ट के लिए बड़ी ओ जटिलता क्या है? मर्ज़ सॉर्ट एक स्थिर है तरह जिसका अर्थ है कि एक सरणी में एक ही तत्व एक दूसरे के संबंध में अपनी मूल स्थिति बनाए रखता है। कुल समय जटिलता का मर्ज़ सॉर्ट है हे (एन लॉग)। यह अधिक कुशल है क्योंकि यह सबसे खराब स्थिति में भी रनटाइम है हे (nlogn) अंतरिक्ष जटिलता का मर्ज़ सॉर्ट है हे (एन)।

सबसे खराब स्थिति में मर्ज सॉर्ट की जटिलता क्या है?

एन * लॉग (एन)

मर्ज सॉर्ट कितनी तुलना करता है?

जब हम किसी एक सूची में तत्वों से बाहर निकलते हैं, तो हम शेष तत्वों को के अंतिम स्लॉट में डाल देते हैं क्रमबद्ध सूची। नतीजतन, विलय दो सूचियाँ जिनमें कुल n तत्व हैं, उन्हें अधिकतम n-1. की आवश्यकता होती है तुलना.