[Powered by Google Translate] [இணை வரிசை] [ராப் Bowden - ஹார்வர்ட் பல்கலைக்கழகம்] [இந்த CS50 உள்ளது. - CS50.TV] ஒன்றிணைப்பு வகையான பற்றி பேசலாம். இதுவரை நீங்கள் குமிழி வரிசையாக்கம், செருகும் வரிசையாக்கம், மற்றும் தேர்வு வகையான பார்த்திருக்கிறேன். நான் நன்றாக அர்த்தம் என்ன அலை என் கையை என்ன செய்வாள் என்றாலும், ஒன்றாக்க வகையான பொதுவாக இந்த 3 வகையான எந்த விட சிறப்பாக செயல்படுகிறது. 

ஆனால் ஒன்றிணைப்பு வகையான பற்றி முன், உலகின் 2 வரிசைப்படுத்தப்பட்ட பட்டியலை இணைத்தல் பற்றி பேசுகிறேன். நாம், இந்த மாதிரி, 2 வரிசைப்படுத்தப்பட்ட பட்டியலை எடுத்து செயல்முறை அழைக்கிறேன் அவர்களில் ஒரு வரிசைப்படுத்தப்பட்ட பட்டியலை அவுட் செய்து - பட்டியல்கள் இணைத்தல். எப்படி இதை செய்ய முடியும்? சரி, ஒரு யோசனை தான் மற்ற பட்டியலை இறுதி மீது ஒரு பட்டியலை உறுதியாக உள்ளது இதன் விளைவாக பட்டியலில் வரிசைப்படுத்த. 

இந்த வேலை செய்யும் போது, அது தேவையில்லாத வேலை நிறைய இருக்கிறது. நாம் தான் வரிசைப்படுத்துவதன் விட வேகமாக அதை செய்ய முடியும். ஒரு தவறான எண்ணம் தான் ஒவ்வொரு பட்டியலில் இருந்து மாற்று கப் எடுத்து என்பதை நீங்கள் கவனிக்க. என்று முதலில் அந்த படைப்புகளை போல தோன்றலாம் போது, 16 மற்றும் 23 இடத்தில் இல்லை என்று அறிவிப்பு - நாம் 4, 8, 15, 23, 16 முடிவடையும் என்று செய்து. இந்த ஏனெனில் இணைக்கப்பட்ட பட்டியலில் தொடர்ந்து தோன்றும் வேண்டும் என்று 2 கூறுகள் அதே ஆரம்ப பட்டியலில் உள்ளன. 15 மற்றும் 16 ஆகிய இரண்டு இடது பட்டியலில் உள்ளன. தந்திரம் இரண்டு பட்டியல்களை ஏற்கனவே வரிசையாக்கம் என்பதை பயன்படுத்தி கொள்ள வேண்டும். அதாவது நாம் இருவரும் பட்டியல்கள் முதல் கூறுகள் பார் என்றால் - இங்கே, 4 மற்றும் 8 - அவற்றில் ஒன்று கூட இணைக்கப்பட்ட பட்டியலில் முதல் உறுப்பு இருக்க வேண்டும். சரி, அது ஏன்? இந்த பட்டியல்களில் இருவரும் ஏற்கனவே வரிசையாக்கம், நாங்கள் 2 பட்டியலை இணைத்து போது மற்றும் 4 அல்லது 8 அல்லது சிறிய உறுப்பு இருக்க வேண்டும். இந்த வழக்கில், சிறிய, 4 எனவே 4 எடுத்து எங்கள் இணைக்கப்பட்ட பட்டியலில் முதல் உறுப்பு செய்யலாம். இப்போது நாம் முதல் பட்டியலில் மீதமுள்ள 3 கூறுகளை சேர்ப்பின் தொடர்ந்து இரண்டாவது பட்டியலில் 4 கூறுகள். 

மீண்டும், நாம் மட்டும் இரண்டு பட்டியல்களை முதல் உறுப்பு பார்க்க வேண்டும். 2 சிறிய எங்கள் இணைக்கப்பட்ட பட்டியலில் இரண்டாவது உறுப்பு இருக்க வேண்டும். இந்த நேரத்தில், 8 மற்றும் 15 இடையே மிகச்சிறிய 8, மற்றும் நாம் செருக என்று எங்கள் வரிசையில் பட்டியலில் இரண்டாவது உறுப்பு. நாங்கள் இருவரும் பட்டியல்கள் முதல் கூறுகள் ஒப்பிட்டு தொடரலாம் மற்றும் 2 சிறிய நீக்கும். 15 மற்றும் 23, 15 ஒப்பிட்டு சிறிய மற்றும் அதனால் நம்முடைய மூன்றாவது உறுப்பு ஆகும். இப்போது 16 ஒப்பிட்டு மற்றும் 23, 16 சிறியதாக இருக்கும். அந்த நான்காவது உறுப்பு தான். 

2 கூறுகள் ஒரு வரிசையில் அதே பட்டியலில் இருந்து வந்தது என்பதை கவனியுங்கள். இது ஏன் இணைக்கப்பட்ட பட்டியலில் 2 பட்டியல்கள் இருந்து தான் மாற்று உறுப்புகள் முடியாது. 50 மற்றும் 23, 23 ஒப்பிட்டு சிறிய, எனவே நாம் அந்த தேர்வு. 50 மற்றும் 42 இடையே, 42 சிறியதாக இருக்கும். 50 மற்றும் 108 இடையில், 50 சிறியதாக இருக்கும். மேலும், இறுதியாக, நாம் மட்டும் 108 வேண்டும், அது எங்கள் பட்டியலில் இறுதியில் போக வேண்டும். நாம் ஒரு நல்ல, வரிசைப்படுத்தப்பட்ட பட்டியலை என்று பாருங்கள். நாங்கள் 2 பட்டியல்கள் முதல் 2 உறுப்புகள் ஒப்பிடுகையில் ஒவ்வொரு முறையும் நாம் இணைக்கப்பட்ட பட்டியலில் அடுத்த உறுப்பு தீர்மானிக்க முடிந்தது. இந்த, என்றால் இறுதி பட்டியல் n இங்கே 8 எங்கே n எண்கள், கொண்டுள்ளது என்று அர்த்தம் நாம் சரியான இடத்தில் அந்த எண்கள் அனைத்தையும் பெற மிக n ஒப்பீடுகள் தேவை. அத்தகைய வழிமுறை, நேரியல் நேரம் இயக்க கூறப்படுகிறது ஆனால் இங்கே அது பற்றி கவலைப்பட வேண்டாம். 

சேர்ப்பின் நமது வழிமுறையை பயன்படுத்தி, நாம் வேகமாக ஒன்றிணைப்பு வகையான வழிமுறையை செய்யலாம். எனவே, நமது பட்டியல்கள் மீட்டமைக்க வேண்டும். ஒன்றிணைப்பு மாதிரி செயல்பாட்டில் 2 பெரிய படிகள் உள்ளன. முதல், தொடர்ந்து பகுதிகளாக கப் பட்டியலில் பிரிந்தது நாம் வெறும் 1 கப் கொண்ட பட்டியல்கள் ஒரு கொத்து வரை. ஒரு பட்டியல் ஒரு ஒற்றைப்படை எண் கொண்ட என்றால் கவலை வேண்டாம் நீங்கள் அவர்களுக்கு இடையில் ஒரு செய்தபின் சுத்தமான வெட்டு செய்ய முடியாது. நான் தன்னிச்சையாக கூடுதல் கப் உள்ளே சேர்க்க இது பட்டியல் தேர்வு எனவே, தான் இந்த பட்டியலை பிரித்து விட. இப்போது நாம் 2 பட்டியல்கள் வேண்டும். இப்போது நாம் 4 பட்டியல்கள் வேண்டும். 

இப்போது நாம் ஒவ்வொரு பட்டியலில் ஒரு கப் 8 பட்டியல்கள் வேண்டும். அதனால் படி 1 அது தான். படி 2, நாம் மீண்டும் மீண்டும் நாம் கற்று ஒன்றிணைப்பு வழிமுறையை பயன்படுத்தி பட்டியல்களில் ஜோடிகள் ஒன்றாக்க. 108 மற்றும் 15 இணைத்தல், நாம் பட்டியலில் 15, 108 முடிவடையும். 50 மற்றும் 4 இணைத்தல், நாங்கள் 4, 50 முடிவடையும். 8 மற்றும் 42 இணைத்தல், நாம், 8 42 முடிவடையும். மேலும் 23 மற்றும் 16 இணைத்தல், நாம், 16 23 முடிவடையும். இப்போது எங்கள் பட்டியல்கள் அளவு 2 இருக்கும். 4 பட்டியலை ஒவ்வொரு வரிசைப்படுத்தப்பட்ட என்று பாருங்கள். 

எனவே நாம் மீண்டும் பட்டியல்களில் ஜோடிகள் சேர்ப்பின் தொடங்க முடியும். 15 மற்றும் 108 மற்றும் 4 மற்றும் 50 சேர்ப்பு - முதலில் 108, பின்னர் 50, பிறகு 15, 4 எடுத்து. 8, 42 மற்றும் 16, 23, சேர்ப்பு நாம் முதலில் பின்னர் 8, 16, 23, 42 ஆகும். எனவே இப்போது நாம் அளவு 4 வெறும் 2 பட்டியல்கள் உள்ளன, ஒவ்வொன்றும் பிரிக்கப்பட்டுள்ளது. எனவே இப்போது நாம் இந்த 2 பட்டியல்கள் ஒன்றாக்க. முதல் நாங்கள் 4 எடுத்து. நாம் 8 எடுத்து. நாம் 15 மற்றும் பின் பின்னர் 16, 23, 42, 50, 108 ஆகும். நாம் முடித்துவிட்டீர்கள். நாம் இப்போது ஒரு வரிசையில் பட்டியலில் இல்லை. இந்த துல்லியமாக, எவ்வளவு வேகமாக வந்தது? தொழில்நுட்ப அடிப்படையில், ஒன்றிணைப்பு வகையான, ஓ (n log n) ஆகும் குமிழி வரிசையாக்கம், செருகும் வரிசையாக்கம், மற்றும் தேர்ந்தெடுக்கப்பட்ட வரிசையாக்க அனைத்து ஓ என்பவை (n ²). நீங்கள் விரைவில் அறியலாம் என உண்மையில், நீங்கள் ஒரு வகையான கொண்டு வர முடியாது என்று பொது வழக்கில் ஓ (n log n) விட சிறப்பாக செயல்படுகிறது. நீங்கள் இன்னும் அதை பார்க்கவில்லை என்றால், மீண்டும், இந்த பெரிய ஓ குறிமானம் பற்றி கவலைப்பட வேண்டாம். 

நாங்கள் ஒரு பெரிய பட்டியல் வரிசைப்படுத்த வேண்டும் என்றால் இந்த பொருள் என்று குமிழி வரிசையாக்கம், செருகும் வரிசையாக்கம், மற்றும் தேர்வு வகையான திறன் ஆகலாம் அதிக சேர்ப்பு வரிசையாக்கம் விட. ஒன்றாக்குவதை வகையான வேகமாக அனைத்து பட்டியல்கள் வேண்டும் என்று அர்த்தம் இல்லை அல்லது ஒரு குறிப்பிட்ட அளவு கீழ் எந்த ஒரு பட்டியல். எடுத்துக்காட்டாக, செருகும் வரிசையாக்கம் 5 கூறுகளை விட சிறிய அனைத்து பட்டியல்கள் வேகமாக வகையான இருக்கலாம். நடைமுறையில், ஒன்றிணைப்பு வகையான 50 உறுப்புகள் போன்ற சிறிய பட்டியல்கள் வழக்கமாக வேகமாக இருக்கும். 

ஆனால் இந்த கூடுதல் வேகம் ஒரு விலை இல்லாமல் வரவில்லை. நம் மற்ற வகையான போல், எந்த இடத்தில் பட்டியலில் ஒரு பட்டியலை எடுத்து மாற்ற நாம் ஒரு வரிசைப்படுத்தப்பட்ட பட்டியலை பெறும் வரை, ஒன்றிணைப்பு வகையான சில கூடுதல் இடம் தேவை ஒன்றாக 2 பட்டியல்களை இணைக்க. நாம் உடனடியாக இணைக்கப்பட்ட பட்டியலில் சேமிக்க இணைக்கப்பட்டு வருகின்றன என்று பட்டியல் பயன்படுத்த முடியாது நாம் இன்னும் இணைக்கப்பட்டது வேண்டும் என்று கூறுகள் புறக்கணிக்க என்பதால். இந்த இடத்தில் ஒரு விலை ஒரு பிட் உள்ளது, ஆனால் அது வழக்கமாக முடியாதது அல்ல. அந்த பிணைப்பு வகையான அது தான். 

என் பெயர் ராப் Bowden, மற்றும் இந்த CS50 உள்ளது. [CS50.TV] - மற்றும் தேர்வு வகையான. [சிரிக்கிறார்] ஓ, நான் அதை வழங்கி எப்படி மாற்றி, ஏனெனில் மிகவும் என்று எடுத்து வந்தது. இடது பட்டியல். ஒரு எழுத்துப்பிழையா இருந்தது. [Misspoke] நான் ஸ்க்ரீவ்டு - [சிரிக்கிறார்] நான் என்ன தெரியாது -