>> டக் LLOYD: எனவே CS50 உள்ள நாம் பற்றி கற்று சார்டிங் பல்வேறு
வழிமுறைகள் இல்லை.
மற்றும் சில நேரங்களில் அது இருக்க முடியும் வைத்து ஒரு சிறிய தந்திரமான
என்ன வழிமுறை கண்காணிக்க என்ன செய்கிறது.
நாம் உண்மையில் போயிருக்கிறோம் கூட மேற்பரப்பு வெண்ணை
பல தேடி உள்ளன மற்றும் வரிசையாக்க படிமுறைகள்.
எனவே, இந்த வீடியோ நாம் ஒரு சில நிமிடங்கள் எடுக்க
முயற்சி மற்றும் ஒவ்வொரு வழிமுறையை நொதிக்க அதன் முக்கிய கூறுகள் கீழே
எனவே நீங்கள் மிகவும் நினைவில் கொள்ள முடியும் அவர்களை பற்றி முக்கியமான தகவல்
இளவல் முடியும் வேறுபாடுகள், தேவைப்பட்டால்.
>> முதல் தேர்வை நடத்த உள்ளது.
தேர்வு வகையான பின்னால் அடிப்படை யோசனை சிறிய வரிசையாக்கம் செய்யப்படாத உறுப்பு கண்டுபிடிக்க
மற்றும் ஒரு வரிசையில் அதை அதை இடமாற்றம் அந்த வரிசையில் முதல் வரிசையாக்கம் செய்யப்படாத உறுப்பு.
நாம் மோசமான என்று கூறினார் அந்த இயக்க நேரம் n ஸ்கொயர்.
நீங்கள் ஏன் நினைவுகூர வேண்டும் என்றால், எடுக்க ஒரு தேர்வு வகையான வீடியோ பாருங்கள்.
சிறந்த வழக்கு ரன் நேரம் மேலும் ஸ்கொயர் n.
>> குமிழி வரிசையாக்கம் என்று பின்னால் யோசனை ஒரு அருகாமைப் ஜோடிகள் இடமாற்றம் உள்ளது.
அதனால் நீங்கள் உதவுகிறது விசை இங்கே வேறுபாடு நினைவில்.
தேர்வு மாதிரியான, இதுவரை, சிறிய கண்டறிய குமிழி கண்டுபிடிக்க
வகையான அடுத்தடுத்த ஜோடிகள் பரிமாறிக்கொள்ளலாம்.
நாம் அடுத்தடுத்த ஜோடிகள் இடமாற்றம் கூறுகள் அவர்கள் என்றால்
இது திறம்பட, வெளியே ஒழுங்கு வலது, பெரிய உறுப்புகள் கொப்பளிக்கிறது
அதே நேரத்தில் இது தொடங்குகிறது இடது சிறிய உறுப்புகள் செல்ல.
மோசமான வழக்கு ரன் நேரம் குமிழி வரிசையாக்கம் ஸ்கொயர் n.
சிறந்த வழக்கு ரன் நேரம் குமிழி வரிசையாக்கம் n உள்ளது.
ஏனெனில் அந்த சூழ்நிலையில் நாங்கள் உண்மையில்
நாங்கள் கொள்ள தேவை இல்லை என்று எந்த பரிமாற்றங்கள்.
நாம் ஒரே ஒரு செய்ய வேண்டும் அனைத்து n உறுப்புகள் முழுவதும் கடந்து.
>> செருகும் வரிசையாக்கம் இல், இங்கு அடிப்படை யோசனை நகர்கிறது.
என்று, செருகும் வரிசையாக்கம் முக்கிய தான்.
நாம் மூலம் ஒரு முறை விலக போகிறோம் இருந்து வரிசை வலமாக.
நாம் செய்ய மற்றும், நாம் இருக்கிறோம் உறுப்புகள் மாற்ற நடக்கிறது
நாம் ஏற்கனவே அறை செய்ய பார்த்திருக்கிறேன் எங்காவது பொருந்தும் வேண்டும் என்று சிறிய
மீண்டும் அந்த வரிசைப்படுத்தப்பட்ட பகுதியில்.
எனவே நாம் வரிசைப்படுத்தப்பட்ட வரிசை கட்டப்படும், ஒரு வலமாக ஒரு நேரத்தில் உறுப்பு,
மற்றும் நாம் அங்கு செய்ய விஷயங்களை மாற்ற.
என்ற மோசமான ரன் நேரம் செருகும் வரிசையாக்கம் ஸ்கொயர் n.
சிறந்த வழக்கு ரன் நேரம் n.
>> முக்கிய இதுவரை எங்கள் வழிமுறைகளை எந்தவொரு ஒன்றாக்க இங்கே பிரிந்தது ஒன்றாக்க.
நாம் என்பதை, முழு வரிசை பிரிந்தது அது ஆறு கூறுகளை, எட்டு கூறுகள் இருக்கிறது,
10,000 உறுப்புகள் நாங்கள் அதை பிரித்து கீழே அரை மூலம், பாதியாக, பாதியாக,
நாம் வரிசை கீழ் வரை N ஒன்று உறுப்பு வரிசைகள்.
N ஒன்று உறுப்பு வரிசைகள் ஒரு தொகுப்பு.
எனவே நாம் ஒரு தொடங்கியது 1,000-உறுப்பு வரிசை,
நாம் புள்ளி பெற நாம் எங்கே 1,000 ஒரு உறுப்பு வரிசைகள் உள்ளன.
அப்பொழுது நாங்கள் அவர்கள் துணை வரிசைகள் ஒன்றாக்க தொடங்கும் மீண்டும் ஒன்றாக சரியான வரிசையில்.
நாம் இரண்டு ஒரு உறுப்பு வரிசைகள் எடுக்கிறோம் மற்றும் இரண்டு உறுப்பு வரிசை உருவாக்க.
நாம் இரண்டு இரண்டு உறுப்பு வரிசைகள் எடுக்கிறோம் மற்றும் ஒரு நான்கு உறுப்பு வரிசை உருவாக்க
அதனால் மற்றும் அதனால் நாம் நான் வரை மீண்டும் ஒரு n, உறுப்பு வரிசை மீண்டும்.
>> என்ற மோசமான ரன் நேரம் ஒன்றிணைப்பு வகையான n முறை பதிவு n.
நாம் n உறுப்புகள் இல்லை, ஆனால் இந்த மீண்டும் சேர்தலின் செயல்முறை
பதிவு n நடவடிக்கைகளை பெற ஒரு முழு வரிசையை மீண்டும்.
நேரம் இயக்க சிறந்த வழக்கு கூட n பதிவு ஆகிறது N இந்த செயல்முறை மிகவும் இல்லை, ஏனெனில்
வரிசை இருந்தது என்பதை கவலை வரிசைப்படுத்தப்பட்ட அல்லது இல்லை தொடங்க.
செயல்முறை இருக்கிறது, அதே தான் குறுகிய சுற்று விஷயங்களை வழிவகையும் இல்லை.
எனவே n மோசமான வழக்கில் n log, n, சிறந்த வழக்கில் n log.
>> நாம் இரண்டு பற்றி பேசினார் நெறிமுறைகள் தேடி.
எனவே நேரியல் தேடல் தேடி பற்றி.
நாம் வரிசை முழுவதும் தொடர ஒரு முறை, இடது இருந்து வலது,
பல கண்டுபிடிக்க முயற்சி என்று நாம் தேடும்.
மோசமான ரன் நேரம் n, பெரிய ஓ உள்ளது.
அது தேடி எங்களுக்கு ஆகலாம் ஒவ்வொரு உறுப்பு முழுவதும்
நாங்கள் தேடும் உறுப்பு கண்டுபிடிக்க , அல்லது கடந்த நிலையில்,
அல்லது இல்லவே இல்லை.
ஆனால் நாம் வரை என்பதை எங்களால் உறுதிப்படுத்த முடியாது நாங்கள் எல்லாம் பார்த்துவிட்டேன்.
சிறந்த வழக்கு மீ, நாங்கள் உடனடியாக கண்டுபிடிக்கிறோம்.
சிறந்த வழக்கு ரன் நேரம் நேரியல் தேடல் 1 ஒமேகா உள்ளது.
>> இறுதியாக, பைனரி தேடல், அங்கு இருந்தது இது வகைப்படுத்தப்பட்ட வரிசை தேவைப்படுகிறது.
என்று ஒரு மிக நினைவில் முக்கியமான கருத்தில்
பைனரி தேடல் பணிபுரியும் போது.
அது அதை பயன்படுத்தி ஒரு முன்நிபந்தனை தான் நீங்கள் மூலம் தேடும் அந்த வரிசையில்
வரிசைப்படுத்தப்பட்ட வேண்டும்.
இல்லையெனில், முக்கிய பிளவை உள்ளது.
அரை வரிசை பிரிந்தது மற்றும் உறுப்புகள் பாதிக்கும் அகற்ற
ஒவ்வொரு முறையும் நீங்கள் தொடரும்போது.
ஏனெனில் இந்த பிளவை மற்றும் அரை அணுகுமுறையில் பிளக்கும் விஷயங்கள்,
மோசமான ரன் நேரம் பைனரி தேடல் ஆகிறது
கணிசமாக இது, n log ஒருபடி தேடல் n விட.
சிறந்த வழக்கு ரன் நேரம் இன்னும் ஒன்றாகும்.
>> நாம் உடனடியாக அதை கண்டுபிடிக்க வேண்டும் முதல் முறையாக நாம், ஒரு பிரிவு செய்ய, ஆனால்
மீண்டும், அந்த நினைவு பைனரி தேடல் என்றாலும்
நேரியல் தேடல் விட கணிசமாக சிறந்த பதிவு என்ற தகுதியினால் லோக் n எதிராக,
நீங்கள் வேலை மூலம் செல்ல வேண்டும் முதலில் உங்கள் வரிசை வரிசைப்படுத்த எந்த
பொறுத்து, அது குறைவாக இருக்கும் வரிசைப்படுத்தப்பட்ட தேடி அளவை.
>> நான் டக் லாயிட் நான், இந்த CS50 உள்ளது.