कम्प्युटर विज्ञान एल्गोरिदम र डेटा संरचनाहरूको जटिलताहरू बुझ्नको बारेमा हो।
तपाईंसँग क्रमबद्ध गर्न आवश्यक वस्तुहरूको सूची छ, तर तपाईंसँग थप जटिल क्रमबद्ध एल्गोरिदम प्रयोग गर्न समय वा स्रोतहरू छैनन्।
सम्मिलन क्रमबद्ध गर्ने सरल एल्गोरिदम मध्ये एक हो, तर यो ठूला सूचीहरूको लागि ढिलो हुन सक्छ।
सजिलो कार्यान्वयन र समझले यो विधि प्रोग्रामरहरू बीच मनपर्ने बनाएको छ। यो साना सूचीहरूको लागि उपयुक्त छ वा जब तपाईंलाई द्रुत समाधान चाहिन्छ।
यस ब्लग पोष्टमा, हामी सम्मिलन क्रमबद्धको समय जटिलता हेर्नेछौं। यो एल्गोरिथ्म arrays क्रमबद्ध गर्न प्रयोग गरिन्छ, र यो O(n) को रनटाइम छ2)। यसको मतलब समय जटिलता array को आकार संग बढ्छ।
यद्यपि, यो एल्गोरिदम अन्य क्रमबद्ध एल्गोरिदमहरू भन्दा छिटो हुन सक्छ, जस्तै Quicksort।
सम्मिलन क्रमबद्ध कसरी काम गर्छ भन्ने बारे नजिकबाट हेरौं!
सम्मिलन क्रमबद्ध एल्गोरिथ्म के हो?
एक पटकमा एक तत्व, सम्मिलन क्रमले क्रमबद्ध एरे उत्पन्न गर्दछ, जसलाई प्राय: सूची भनिन्छ।
उदाहरण को लागी, क्रमबद्ध गर्न को लागी जटिल कम्प्यूटर प्रोग्रामहरु जस्तै कम्पाइलरहरु मा लागू गरिन्छ, जहाँ टोकन को क्रम कार्यक्रम को व्याख्या को लागी महत्वपूर्ण छ।
कसरी सम्मिलन क्रमबद्ध काम गर्छ?
जब हामी एरे क्रमबद्ध गर्न सम्मिलन क्रम प्रयोग गर्छौं, एल्गोरिदम सूचीमा सबैभन्दा सानो वस्तु फेला पारेर सही स्थितिमा सम्मिलित गरेर सुरु हुन्छ।
यसले त्यसपछि अर्को सानो वस्तु फेला पार्छ र यसलाई सही स्थितिमा घुसाउँछ, र यस्तै।
एल्गोरिदमले सूचीको माध्यमबाट लुप गरेर काम गर्दछ, प्रत्येक वस्तुलाई यो भन्दा अगाडि आएको एकसँग तुलना गर्दछ।
यदि वस्तुहरू गलत क्रममा छन् भने, एल्गोरिदमले तिनीहरूलाई स्वैप गर्दछ। त्यसपछि सूची क्रमबद्ध गरिएको छ कि छैन भनेर जाँच गर्दछ, र यदि यो छ भने, एल्गोरिथ्म समाप्त हुन्छ।
अभ्यासमा, सम्मिलन क्रम प्रायः कोडका केही लाइनहरू प्रयोग गरेर लागू गरिन्छ, यसलाई साना एरेहरू क्रमबद्ध गर्न लोकप्रिय छनोट बनाइन्छ। यद्यपि, यो एल्गोरिथ्म प्रयोग गर्दा समय जटिलतालाई विचार गर्नुपर्छ।
उदाहरण:
यहाँ सम्मिलन क्रमबद्ध कसरी काम गर्दछ भन्ने उदाहरण छ। हामी निम्न एरे प्रयोग गर्नेछौं:
1, 2, 3, 4, 5, 6
एल्गोरिदम सूचीमा सबैभन्दा सानो वस्तु फेला पारेर सुरु हुन्छ, जुन 1 हो। त्यसपछि यसलाई सही स्थिति, पहिलो स्थानमा घुसाउँछ। यसले त्यसपछि अर्को सबैभन्दा सानो वस्तु फेला पार्छ, जुन २ हो। यसले यसलाई सही स्थानमा घुसाउँछ, जुन दोस्रो स्थान हो।
यसले त्यसपछि अर्को सबैभन्दा सानो वस्तु फेला पार्छ, जुन 3 हो। यसले यसलाई सही स्थानमा घुसाउँछ, जुन तेस्रो स्थान हो।
यसले त्यसपछि अर्को सबैभन्दा सानो वस्तु फेला पार्छ, जुन 4 हो। यसले यसलाई सही स्थितिमा घुसाउँछ, जुन चौथो स्थान हो, र यस्तै। सूची अब क्रमबद्ध छ!
हामी उदाहरणबाट देख्न सक्छौं कि एल्गोरिदमले सूची क्रमबद्ध गर्न छवटा तुलना र स्वैप लिन्छ। यो किनभने यो n लिन्छ2 n वस्तुहरूको सूची क्रमबद्ध गर्न तुलना र स्वैप। यस अवस्थामा, n = 6।
कसरी सम्मिलन क्रमबद्ध समय जटिलता सुधार गर्ने?
जबकि सम्मिलन क्रमको O(n.) को रनटाइम हुन्छ2), यसलाई राम्रो क्रमबद्ध एल्गोरिदम प्रयोग गरेर सुधार गर्न सकिन्छ, जस्तै Quicksort।
Quicksort सँग O(n log n) रनटाइम छ, जुन O(n) भन्दा धेरै छिटो छ2).
यद्यपि, केहि अवस्थामा, सम्मिलन क्रमबद्ध द्रुत क्रम भन्दा छिटो हुन सक्छ।
उदाहरण को लागी, यदि सूची पहिले नै क्रम मा छ भने, सम्मिलन क्रमबद्ध द्रुत क्रम भन्दा कम समय लाग्नेछ।
अभ्यासमा, सम्मिलन क्रम प्रायः कोडका केही लाइनहरू प्रयोग गरेर लागू गरिन्छ, यसलाई साना एरेहरू क्रमबद्ध गर्न लोकप्रिय छनोट बनाइन्छ।
यद्यपि, यो एल्गोरिथ्म प्रयोग गर्दा समय जटिलतालाई विचार गर्नुपर्छ।
समय जटिलताहरू
सबैभन्दा खराब केस जटिलता O(n2):
समय जटिलता array को आकार संग बढ्छ। यसले n लिन्छ2 n वस्तुहरूको सूची क्रमबद्ध गर्न तुलना र स्वैप।
उदाहरणका लागि, यदि हामीसँग आकार 1000 को एरे छ भने, एल्गोरिदमले एरे क्रमबद्ध गर्न 1,000,000 तुलना र स्वैप लिनेछ।
उत्तम केस जटिलता O(n):
समय जटिलता इनपुट एरे को आकार जस्तै छ। म
n वस्तुहरूको सूची क्रमबद्ध गर्न t ले n तुलनाहरू र स्वैपहरू लिन्छ। उदाहरणका लागि, साइज ५ को एरेलाई विचार गर्नुहोस्। एल्गोरिदमले एरे क्रमबद्ध गर्न पाँचवटा तुलना र स्वैप लिनेछ।
औसत केस जटिलता O(n2):
समय जटिलता यस मामला मा सबै भन्दा खराब र सबै भन्दा राम्रो मामला जटिलताहरु बीच छ।
यसले n लिन्छ2 n वस्तुहरूको सूची क्रमबद्ध गर्न तुलना र स्वैप।
यसरी, सम्मिलन क्रमबद्ध एक स्थिर क्रमबद्ध एल्गोरिथ्म हो।
किन सम्मिलन क्रमबद्ध स्थिर छ?
प्रविष्टि क्रम स्थिर छ किनभने यसले इनपुट एरेमा समान तत्वहरूको क्रम सुरक्षित गर्दछ।
यो धेरै अनुप्रयोगहरूको लागि महत्त्वपूर्ण छ, जस्तै डेटा पुन: प्राप्ति वा वित्तीय विश्लेषण। उदाहरणका लागि, यदि हामीसँग संख्याहरूको दुईवटा सूचीहरू छन् र तिनीहरूलाई तुलना गर्न चाहन्छौं भने, हामीले तत्वहरूको क्रम सुरक्षित छ भनी सुनिश्चित गर्न आवश्यक छ।
यदि सूचीहरू क्रमबद्ध गरिएको छैन भने, हामी तिनीहरूलाई सही रूपमा तुलना गर्दैनौं।
जवाफ छाड्नुस्