[Powered by Google Translate] டாமி: உலகின் தேர்வு வகையான பாருங்கள், ஒரு படிமுறை விடு
எண்கள் பட்டியல் எடுத்து அவர்களை வரிசைப்படுத்த.
ஒரு வழிமுறை, நினைவில், வெறுமனே ஒரு படி மூலம் நடவடிக்கை
ஒரு பணியை நிறைவேற்றும் நடைமுறைகள்.
தேர்வு வகையான பின்னால் அடிப்படை கருத்து பிரித்து உள்ளது
இரண்டு பகுதிகள் எங்கள் பட்டியலில் -
ஒரு வரிசைப்படுத்தப்பட்ட பகுதி மற்றும் ஒரு வரிசையாக்கம் செய்யப்படாத பகுதி.
படிமுறை ஒவ்வொரு அடியிலும், பல மற்றதற்கு
இறுதியில் வரை வரிசைப்படுத்தப்பட்ட பகுதிக்கு வரிசையாக்கம் செய்யப்படாத பகுதி
முழு பட்டியல் பிரிக்கப்பட்டுள்ளது.
இங்கு ஆறு எண்கள் ஒரு பட்டியல் -
23, 42, 4, 16, 8, மற்றும் 15.
இப்போது முழு பட்டியலை வரிசையாக்கம் செய்யப்படாத கருதப்படுகிறது.
16 போன்ற பல ஏற்கனவே அதன் சரியான இருக்கலாம் கூட
இடம், எங்கள் வழிமுறை வரை என்று தெரிந்தும் வழி உள்ளது
முழு பட்டியல் பிரிக்கப்பட்டுள்ளது.
நாம் அடுக்க வரை நாம் வரிசையாக்கம் செய்யப்படாத வேண்டும் ஒவ்வொரு எண் நினைப்பாய்
அது நம்மை.
நாம் பட்டியல் ஏறுவரிசையில் இருக்க வேண்டும் என்று.
எனவே நாங்கள் எங்கள் பட்டியலில் வரிசைப்படுத்தப்பட்ட பகுதியை உருவாக்க வேண்டும் என்று நான் நினைக்கிறேன்
இடது இருந்து வலது, மிக பெரிய ஒரு சிறிய.
அதை செய்ய, நாங்கள் குறைந்தபட்ச வரிசையாக்கம் செய்யப்படாத உறுப்பு கண்டுபிடிக்க வேண்டும்
மற்றும் வரிசைப்படுத்தப்பட்ட பகுதியை இறுதியில் அதை வைத்து.
இந்த பட்டியல் வரிசையில் அல்ல என்பதால், அதை செய்ய ஒரே வழி ஆகும்
நினைவு, வரிசையாக்கம் செய்யப்படாத பகுதியில் ஒவ்வொரு உறுப்பு பாருங்கள்
உறுப்பு குறைந்த மற்றும் ஒப்பிட்டு இது
என்று ஒவ்வொரு உறுப்பு.
நாம் முதல் 23 பார்க்க வேண்டும்.
இந்த நாங்கள் பார்த்த முதல் உறுப்பு, எனவே நாம் ஞாபகம்
குறைந்தபட்ச அது.
அடுத்த நாங்கள் 42 பார்க்க வேண்டும்.
42 23 விட பெரியதாக உள்ளது, எனவே 23 இன்னும் குறைந்தபட்ச உள்ளது.
அடுத்த 23 குறைவாக உள்ளது 4, எனவே நாம் 4 ஞாபகம்
புதிய குறைந்தது.
அடுத்த எனவே 4, 4 விட பெரிய இது 16 ஆகும்
இன்னும் குறைந்தது ஆகும்.
8 4 விட பெரியதாக உள்ளது, மற்றும் 15 4 அளவை விட பெரிய, 4 இருக்க வேண்டும் என்று
சிறிய வரிசையாக்கம் செய்யப்படாத உறுப்பு.
அதனால் கூட மனிதர்களை நாம் உடனடியாக 4 என்று பார்க்கலாம்
குறைந்தபட்ச உறுப்பு, நமது வழிமுறையை பார்க்க வேண்டும்
நாம் 4 காணப்படும் பின்னரும் கூட, ஒவ்வொரு வரிசையாக்கம் செய்யப்படாத உறுப்பு, -
குறைந்தபட்ச உறுப்பு.
எனவே இப்போது நாம் குறைந்தபட்ச உறுப்பு, 4 கண்டுபிடித்தோம் என்று, நாங்கள் விரும்பவில்லை வேண்டும்
பட்டியல் வரிசையில் பகுதி நகர்த்த வேண்டும்.
இந்த முதல் படி என்பதால், இந்த நாங்கள் 4 வைக்க வேண்டும் என்றால்
பட்டியலில் ஆரம்பத்தில்.
இப்போது 23 ஆக, பட்டியலில் ஆரம்பத்தில் உள்ளது
4 மற்றும் 23 இடமாற்றம் செய்யலாம்.
எனவே இப்போது எங்கள் பட்டியலில் இந்த தெரிகிறது.
இது ஏனெனில் நாங்கள், 4 அதன் இறுதி இடத்தில் இருக்க வேண்டும் என்று
ஆரம்பத்தில் சிறிய உறுப்பு மற்றும் உறுப்பு இரண்டு
பட்டியல்.
நாம் அதை மீண்டும் செல்ல தேவையில்லை அப்படியென்றால்.
எனவே மற்றொரு உறுப்பு சேர்க்க இந்த செயல்முறை மீண்டும் நாம்
பட்டியல் வரிசையில் பகுதி.
அதை தான் நாங்கள் 4 பார்க்க தேவையில்லை என்று
ஏற்கனவே வரிசையாக்கம்.
எனவே நாம் ஞாபகம் இதில், 42 மணிக்கு தொடங்கும்
குறைந்தபட்ச உறுப்பு.
எனவே அடுத்த நாங்கள் 42 க்கும் குறைவான இது 23 பாருங்கள், அதனால் நான் நாம்
23 புதிய குறைந்தபட்ச ஞாபகம்.
அடுத்த நாம், குறைவான 23 இது 16 பார்க்க
16 புதிய குறைந்தபட்ச உள்ளது.
இப்போது நாம், குறைவான 16 ஆகும் 8 பாருங்கள்
8 புதிய குறைந்தபட்ச உள்ளது.
இறுதியில் 8 குறைவாக 15, எனவே நாம் 8 குறைந்தபட்ச என்று
வரிசையாக்கம் செய்யப்படாத உறுப்பு.
அதனால் நாம் வரிசையில் 8 சேர்க்க வேண்டும் என்பதாகும்
பட்டியல் பகுதி.
இப்போது 4 மட்டுமே வரிசைப்படுத்தப்பட்ட உறுப்பு, எனவே நாம் வைக்க வேண்டும்
4 முதல் 8 அடுத்த.
42 ல் இருந்து ஒரு வரிசையாக்கம் செய்யப்படாத பகுதியில் முதல் உறுப்பு ஆகும்
பட்டியலில், நாங்கள் 42 மற்றும் 8 மாற்ற வேண்டும் நான்.
எனவே இப்போது எங்கள் பட்டியலில் இந்த தெரிகிறது.
4 மற்றும் 8 பட்டியலை வரிசையாக்கம் பகுதியை பிரதிநிதித்துவம், மற்றும்
மீதமுள்ள எண்கள் வரிசையாக்கம் செய்யப்படாத பிரதிநிதித்துவம்
பட்டியல் பகுதி.
எனவே மற்றொரு மறு செய்கை தொடர அனுமதிக்க.
நாம் பார்க்க வேண்டிய அவசியம் இல்லை என்பதால், நாம், 23 இந்த நேரத்தில் தொடங்க
4 மற்றும் இனி 8 அவர்கள் தான் காரணம்
ஏற்கனவே வரிசையாக்கம்.
16 க்கும் குறைவான 23, எனவே நாம் ஞாபகம்
புதிய குறைந்தபட்சம் 16.
15 இருக்க வேண்டும், எனவே, 16 க்கும் குறைவான 42, ஆனால் 15 க்கும் குறைவான 16 ஆகும்
குறைந்தபட்ச வரிசையாக்கம் செய்யப்படாத உறுப்பு.
எனவே இப்போது நாம் 15 மற்றும் 23 இடமாற்றம் வேண்டும்
இந்த பட்டியல் கொடுக்க.
பட்டியல் வரிசையில் பகுதி 4, 8 மற்றும் 15 ஆகும், மற்றும்
இந்த கூறுகள் இன்னும் வரிசையாக்கம் செய்யப்படாத.
ஆனால் அது மிகவும் நடக்கிறது என்று அடுத்த வரிசையாக்கம் செய்யப்படாத உறுப்பு, 16,
ஏற்கனவே பிரிக்கப்பட்டுள்ளது.
இருப்பினும், என்று எங்கள் வழிமுறை வேறு வழியில்லை என்று 16
ஏற்கனவே அதன் சரியான இடத்தில் உள்ளது, எனவே நாம் இன்னும் வேண்டும்
அதே செயற்பாட்டை மீண்டும் செய்க.
அதனால், நாங்கள் 16 க்கும் குறைவான 42 என்று பார்க்க, மற்றும் 16 க்கும் குறைவான 23 ஆகும்
16 குறைந்தபட்ச உறுப்பு இருக்க வேண்டும்.
அது தன்னை இந்த உறுப்பு மாற்ற முடியாது, நாம் மிகவும்
வெறுமனே இந்த இடத்தில் விட்டு.
எனவே நாம் நமது வழிமுறையின் ஒரு பாஸ் வேண்டும்.
42 23 விட அதிகமாக உள்ளது, எனவே 23 இருக்க வேண்டும்
குறைந்தபட்ச வரிசையாக்கம் செய்யப்படாத உறுப்பு.
ஒருமுறை நாங்கள் எங்கள் இறுதி முடிவடையும், 23 மற்றும் 42 இடமாற்றம்
வரிசையில் பட்டியல் -
4, 8, 15, 16, 23, 42.
நாம் அது முதல் 42 சரியான இடத்தில் இருக்க வேண்டும் என்று
ஒரே உறுப்பு விட்டு, அந்த தேர்வு வகையான தான்.
நாம் இப்போது சில நமது வழிமுறையை முறைப்படுத்துவது
சூடோகுறியீடு.
வரி ஒரு, நாங்கள் மேல் ஒருங்கிணைக்க வேண்டும் என்று பார்க்கலாம்
பட்டியலில் ஒவ்வொரு உறுப்பு.
கடந்த உறுப்பு தவிர, முதல் 1 உறுப்பு
பட்டியலில் ஏற்கனவே பிரிக்கப்பட்டுள்ளது.
வரி இரண்டு, நாம் வரிசையாக்கம் செய்யப்படாத முதல் உறுப்பு கருத்தில்
நாம் செய்தது போல் பட்டியலில் பகுதி, குறைந்தபட்ச வேண்டும்
எடுத்துக்காட்டாக, அதனால் நாம் ஒப்பிட்டு ஏதாவது.
வரி மூன்று நாம் மீண்டும் கூறு இதில் இரண்டாவது வளைய தொடங்குகிறது
ஒவ்வொரு வரிசையாக்கம் செய்யப்படாத உறுப்பு.
நாம் என்று நான் மீண்டும் பிறகு, வரிசைப்படுத்தப்பட்ட பகுதி
எங்கள் பட்டியலில் ஒவ்வொரு படியாக இருந்து அதை நான் உறுப்புகள் வேண்டும்
வகையான ஒரு உறுப்பு.
எனவே முதல் வரிசையாக்கம் செய்யப்படாத உறுப்பு நிலையை நான் பிளஸ் 1 ல் இருக்க வேண்டும்.
வரி நான்கு, நாங்கள் குறைந்தபட்ச தற்போதைய உறுப்பு ஒப்பிட்டு
நாம் இதுவரை பார்த்த அந்த உறுப்பு.
தற்போதைய உறுப்பு குறைந்தபட்ச விட சிறியதாக இருந்தால்,
உறுப்பு, நாம் புதிய தற்போதைய உறுப்பு நினைவில்
வரி ஐந்து குறைந்த பட்ச.
இறுதியாக, கோடுகள் ஆறு மற்றும் ஏழு, நாங்கள் குறைந்தபட்ச இடமாற்றம்
இதனால் முதல் வரிசையாக்கம் செய்யப்படாத உறுப்பு கொண்ட உறுப்பு,
பட்டியல் வரிசையில் பகுதி சேர்ப்பதன்.
நாம் ஒரு வழிமுறை உண்டு முறை, ஒரு முக்கியமான கேள்வி கேட்க
நம்மை மென்பொருள் என்று எவ்வளவு காலம் எடுக்கும்?
நாம் முதல் கேள்வி கேட்கிறேன், அது எவ்வளவு நேரம் இந்த எடுக்கிறது
படிமுறை மிக மோசமான நிலையில் இயக்க?
நாம் இந்த ஓட்டம் பிரதிநிதித்துவம்
பெரிய ஓ குறிமானம் நேரம்.
குறைந்தபட்ச வரிசையாக்கம் செய்யப்படாத உறுப்பு தீர்மானிக்கும் பொருட்டு, நாம்
அடிப்படையில் இந்த பட்டியல் ஒவ்வொரு உறுப்பு ஒப்பிட்டு வேண்டும்
பட்டியலில் ஒவ்வொரு மற்ற உறுப்பு.
உள்ளுணர்வாக, n ஸ்கொயர் நடவடிக்கையின் ஒரு ஓ போல் தெரிகிறது.
எங்கள் சூடோகுறியீடு பார்த்து, நாங்கள் உள்ளே காக்கப்பட்ட ஒரு வளைய வேண்டும்
ஒரு ஓ போன்ற உண்மையில் ஒலிகளை இதில் இன்னொரு சுழற்சி,
n ஸ்கொயர் செயல்பாடு.
எனினும், நாம் பார்க்க வேண்டும் என்று நினைவில்
குறைந்தபட்ச வரிசையாக்கம் செய்யப்படாத உறுப்பு நிர்ணயிக்கும் போது முழு பட்டியல்?
நாம் 4 வரிசைப்படுத்தப்பட்ட என்று தெரியும் முறை, உதாரணமாக, நாம் செய்யவில்லை
மீண்டும் பார்க்க வேண்டும்.
இந்த இயங்கும் முறை, அதனால் என்ன?
நீளம் 6 எங்கள் பட்டியலில், நாங்கள் ஐந்து செய்ய தேவை
முதல் உறுப்பு ஒப்பீடுகளின், நான்கு ஒப்பீடுகள்
இரண்டாவது உறுப்பு, மற்றும் பல.
அந்த வழிமுறைகளை எண்ணிக்கை தொகை ஆகும்
1 முதல் பட்டியல் கழித்து 1 நீளம் இன்டீஜர்கள்.
நாம் ஒரு கூட்டுத்தொகை இந்த பிரதிநிதித்துவம் முடியும்.
நாம் இங்கே கூட்டுத்தொகைகளின் போக மாட்டேன்.
ஆனால் இந்த கூட்டுத்தொகை n முறை சமமாக இருக்கும் என்று மாறும்
n கழித்து 2 மேல் 1.
அல்லது சமமான, n 2 மேல் கழித்து n 2 மேல் சரி.
எந்த அறிகுறியும் இயக்க பற்றி பேசும் போது, இந்த n ஸ்கொயர் கால
இந்த n கால ஆதிக்கம் செலுத்த போகிறது.
அதனால் தேர்வு வகையான n ஸ்கொயர் ஓ உள்ளது.
நமது எடுத்துக்காட்டில், தேர்வு வகையான இன்னும் தேவை என்று நினைவு
சரி என்றால் ஏற்கனவே வரிசையாக்கம் என்று ஒரு எண்
நகர்ந்து வேண்டும்.
அதனால் என்று நாம் ஏற்கனவே மேல் தேர்வு வகையான ஓடி என்றால்
பட்டியல் வரிசையில், அது போன்ற நடவடிக்கைகளை அதே எண்ணை தேவை
முற்றிலும் வரிசையாக்கம் செய்யப்படாத பட்டியலில் மேல் இயங்கும் போது என்று.
அதனால் தேர்வு வகையான, ஸ்கொயர் n ஒரு சிறந்த வழக்கு செயல்திறன் உள்ளது
இதில் நாம் ஒமேகா n ஸ்கொயர் மூலம் பிரதிநிதித்துவம்.
அந்த தேர்வு வகையான அது தான்.
நாம் பல படிமுறைகளின் ஒரு
ஒரு பட்டியல் வரிசைப்படுத்த பயன்படுத்தும்.
என் பெயர் டாமி, மற்றும் இந்த cs50 உள்ளது.