[Powered by Google Translate] [கருத்தரங்க: தொழில்நுட்ப செய்திகள்]
[கென்னி யூ, ஹார்வர்ட் பல்கலைக்கழகம்]
[இந்த CS50 உள்ளது.] [CS50.TV]
Hi அனைவருக்கும், நான் கென்னி இருக்கிறேன். நான் தற்போது ஒரு இளைய படிக்கும் கணினி அறிவியல் தான்.
நான் ஒரு முன்னாள் சிஎஸ் TF இருக்கிறேன், மற்றும் நான் ஒரு underclassman போது நான் இந்த கூறியிருபேன்
நான் இந்த கருத்தரங்கில் தருகிறேன் ஏன் என்று.
அதனால் நான் உங்களுக்கு பிடிக்கும் என்று நம்புகிறேன்.
இந்த கருத்தரங்கு, தொழில் நுட்ப நேர்முக பற்றி
மற்றும் அனைத்து என் வளங்கள், இந்த இணைப்பை காணலாம்
இங்கே இந்த இணைப்பை, வளங்களை ஒரு ஜோடி.
எனவே நான் சில பிரச்சினைகள், உண்மையில், பிரச்சினைகள் பட்டியலை கொடுத்தார்.
நாம் குறிப்புகள் காணலாம் அங்கு ஒரு பொது வளங்கள் பக்கம்
ஒரு பேட்டியில் தயாராக எப்படி,
நீ ஒரு உண்மையான பேட்டி போது என்ன செய்ய வேண்டும் என்பது பற்றிய குறிப்புக்கள்,
அத்துடன் எதிர்கால சிக்கல்கள் மற்றும் வளங்களை அணுக எப்படி.
இது அனைத்து இணைய.
மேலும் இந்த கருத்தரங்கு, ஒரு நிபந்தனைகள், முகவுரையில் வேண்டும்
இந்த கூடாது - உங்கள் பேட்டி தயாரிப்பு
இந்த பட்டியலில் மட்டுமே கூடாது.
இது, ஒரு வழிகாட்டியாக இருக்கும் பொருள்
நீங்கள் நிச்சயமாக, நான் உப்பு ஒரு தானிய சொல்வது எல்லாம் வேண்டும்
ஆனால் நான் உங்கள் பேட்டி தயாரிப்பு நீ உதவுகிறது எல்லாம் பயன்படுத்த.
>> நான் அடுத்த சில ஸ்லைடுகள் மூலம் துரிதப்படுத்த போகிறேன்
எனவே, நாம் உண்மையான வழக்கு ஆய்வுகள் பெற முடியும்.
ஒரு மென்பொருள் பொறியியல் postion ஒரு பேட்டியில் கட்டமைப்பு,
பொதுவாக இது 30 முதல் 45 நிமிடங்கள்,
நிறுவனம் பொறுத்து பல சுற்றுக்கள்.
பெரும்பாலும் நீங்கள் ஒரு வெள்ளை பலகையில் குறியீட்டு.
அதனால் இந்த மாதிரி, ஆனால் பெரும்பாலும் ஒரு சிறிய அளவில் ஒரு வெள்ளை பலகை.
நீங்கள் ஒரு தொலைபேசி பேட்டியில் சிக்கல் இருந்தால், ஒருவேளை நீங்கள் பயன்படுத்தி
collabedit அல்லது ஒரு Google ஆவணம் அல்லது அவர்கள் நீங்கள் குறியீட்டு வாழ முடியும்
நீங்கள் தொலைபேசி மூலம் பேட்டி போது.
ஒரு பேட்டியில் தன்னை பொதுவாக 2 அல்லது 3 பிரச்சினைகள் இல்லை
உங்கள் கணினி அறிவியல் அறிவு சோதனை.
இது கிட்டத்தட்ட கண்டிப்பாக குறியீட்டு உள்ளடக்கம்.
நீங்கள் பார்ப்பீர்கள் என்று கேள்விகள் வகைகள் வழக்கமாக தரவு கட்டமைப்புகள் மற்றும் வழிமுறைகள் உள்ளன.
மற்றும் பிரச்சினைகள் இந்த வகையான செய்து,
அவர்கள் விரும்பினால், நீங்கள் கேட்க வேண்டும், என்ன நேரம் மற்றும் இடத்தை சிக்கலான, பெரிய ஓ இருக்கிறது?
பெரும்பாலும் அவர்கள் உயர் நிலை கேள்விகளை கேட்க,
எனவே, ஒரு கணினி வடிவமைப்பு
எப்படி நீங்கள் உங்கள் குறியீடு வெளியே போட வேண்டும்?
என்ன இடைமுகங்கள், என்ன வகுப்புகள், நீங்கள் உங்கள் கணினியில் என்ன தொகுதிகள் இல்லை,
இந்த எப்படி ஒன்றாக தொடர்பு என்ன?
எனவே தரவு கட்டமைப்புகள் மற்றும் நெறிமுறைகள் மற்றும் வடிவமைத்தல் அமைப்புகள்.
>> எங்கள் வழக்கு ஆய்வுகள் ல் டைவ் முன் சில பொது குறிப்புகள்.
நான் மிக முக்கிய விதி எப்போதும் சத்தமாக நினைத்து என்று.
நேர்காணலில் உங்கள் சிந்தனை செயல்முறை காட்ட வாய்ப்பு இருக்க வேண்டும்.
பேட்டி அளவிடுவதற்கு நேர்காணல் நிலையில் உள்ளது
எப்படி என்று எப்படி நீங்கள் ஒரு சிக்கல் செல்ல.
நீங்கள் என்ன செய்ய முடியும் மோசமான விஷயம் முழு பேட்டி முழுவதும் இருக்கும் அமைதியாக இருக்கிறது.
என்று மட்டும் இல்லை நல்லது.
நீங்கள் ஒரு கேள்வியை கொடுக்கப்பட்ட போது, நீங்கள் கேள்வி புரிந்து உறுதி செய்ய வேண்டும்.
உங்கள் சொந்த வார்த்தைகளை மீண்டும் கேள்வியை மீண்டும்
முயற்சி முழுமையான ஒரு சில எளிய சோதனை நேரங்களில் வேலை
நீங்கள் கேள்வி புரிந்து என்பதை.
ஒரு சில சோதனை வழக்குகள் மூலம் உழைக்கும் நீங்கள் இந்த பிரச்சனையை எப்படி தீர்ப்பது என்று ஒரு உள்ளுணர்வு அளிக்கும்.
நீங்கள் கூட ஒரு சில முறைகள் நீங்கள் இந்த சிக்கலை தீர்க்க உதவும் கண்டறிய வேண்டும்.
அவர்கள் பெரிய முனையில் அலுக்கவில்லை உள்ளது.
அலுக்கவில்லை.
நேர்முக சவால் ஆகும், ஆனால் நீங்கள் என்ன செய்ய முடியும் மோசமான விஷயம்,
அமைதியாக இருப்பது கூடுதலாக, சரா விரக்தி வேண்டும்.
நீங்கள் ஒரு பேட்டி என்று தோற்றத்தை கொடுக்க விரும்பவில்லை.
ஒன்று என்று நீங்கள் - அதனால், பல மக்கள், அவர்கள் ஒரு பேட்டியில் போக போது,
அவர்கள், முதல் சிறந்த தீர்வு காண முயற்சி முயற்சி
போது உண்மையில், ஒரு glaringly தெளிவான தீர்வு வழக்கமாக உள்ளது.
அது மெதுவாக இருக்கலாம், அது பயனற்றதாக இருக்கும், ஆனால் நீங்கள் அதை கூற வேண்டும்
இப்போது நீங்கள் நல்ல வேலை இது ஒரு தொடக்க புள்ளியாக உள்ளது.
மேலும், தீர்வு சுட்டிக்காட்டி வகையில், மெதுவான
பெரிய ஓ சிக்கலான நேரத்தை அல்லது விண்வெளி சிக்கல்,
நீங்கள் புரிந்துகொள்ள பேட்டி என்று நிரூபிக்கும் முடியும்
இந்த பிரச்சினைகள் குறியீடு எழுதும் போது.
எனவே முதல் எளிய வழிமுறையை கொண்டு வர பயப்படவேண்டாம்
பின்னர் அங்கு இருந்து நல்ல வேலை.
எந்த கேள்விகளுக்கு இதுவரை? சரி.
>> எனவே நாம் நமது முதல் பிரச்சனை தொடர்பாக டைவ்.
"N முழுஎண்களின் வரிசை நிலையில், வரிசை shuffles என்று ஒரு செயல்பாடு எழுத
n முழுஎண்களின் அனைத்து வரிசைமாற்றங்கள் சமமாக வாய்ப்பு உள்ளது என்று இந்த இடத்தில். "
நீங்கள் இன்னும் ஒரு சீரற்ற முழு ஜெனரேட்டர் வேண்டும் கருதி
அந்த அரை வீச்சு, 0 இருந்து நான் ஒரு வரம்பில் ஒரு முழு எண் உருவாக்குகிறது.
எல்லோரும் இந்த கேள்வியை புரிந்து?
நான் உன்னை n முழுஎண்களின் வரிசை கொடுக்க, நான் உங்களுக்கு குலைப்பதை அதை விரும்பவில்லை.
என் அடைவில், நான் என்ன என்பதை ஒரு சில திட்டங்கள் எழுதினார்.
நான், குலைப்பதை 20 தனிமங்களின் வரிசை போகிறேன்
-10 இருந்து +9 வேண்டும்,
நான் இந்த மாதிரி ஒரு பட்டியல் வெளியனுப்புவதில் வேண்டும்.
இந்த என் வரிசைப்படுத்தப்பட்ட உள்ளீடு வரிசை உள்ளது, மற்றும் நீ கலக்கு அதை விரும்பவில்லை.
நாம் மீண்டும் அதை செய்கிறேன்.
எல்லோரும் கேள்வி புரிந்து? சரி.
அதை நீங்கள் தான்.
சில யோசனைகள் என்ன? நீங்கள் n ^ 2, n log n, n அதை செய்ய முடியும்?
பரிந்துரைகள் திறக்க.
சரி. எம்மி பரிந்துரைத்த அதனால் ஒரு யோசனை,,
முதல் 0 20 ஒரு சீரற்ற எண், சீரற்ற முழு, ஒரு வரம்பில் கணக்கிட வேண்டும்.
எனவே எங்கள் அணி 20 நீளம் உள்ளது என்று வைத்து கொள்வோம்.
20 உறுப்புகள் எங்கள் வரைபடம்,
இந்த எங்கள் உள்ளீடு வரிசை ஆகும்.
இப்போது, அவரது கருத்து, ஒரு புதிய அணியை உருவாக்க வேண்டும்
இந்த வெளியீடு வரிசை இருக்கும்.
நான் ரேண்ட் வந்தார் அடிப்படையில் -
நான் இருந்தால் அதனால், 17, தான் சொல்கிறேன்
முதல் நிலைக்கு 17 உறுப்பு நகலெடுக்க.
இப்போது நாங்கள் நீக்க வேண்டும் - நாம் இங்கே அனைத்து கூறுகளும் மாற்ற வேண்டும்
மேல் நாம் முடிவில் ஒரு இடைவெளி மற்றும் நடுத்தர எந்த ஓட்டைகள் என்று.
இப்போது நாம் செயல்முறை மீண்டும்.
இப்போது நாம் 0 மற்றும் 19 இடையேயான ஒரு புதிய சீரற்ற முழு எடுக்க.
நாம் இங்கே ஒரு புதிய நான் இல்லை, நாம் இந்த நிலையில் இந்த உறுப்பு நகலெடுக்க.
பின் நாம் பொருட்களை மாற்ற நாம் நமது முழு புதிய வரிசை வரை நாம் செயல்முறை மீண்டும்.
இந்த வழிமுறையின் ரன் நேரம் என்ன?
சரி, இந்த பாதிப்பை கருத்தில் கொள்வோம்.
நாம் ஒவ்வொரு உறுப்பு மாற்றுவதால்.
இந்த நான் நீக்க போது, நாம் இடது அதற்கு பிறகு அனைத்து தனிமங்களுக்கு.
மற்றும் ஒரு ஓ (n) விலை
ஏனெனில் நாம் முதல் உறுப்பு நீக்க வேண்டும்?
எனவே ஒவ்வொரு நீக்க, நாம் நீக்க -
ஒவ்வொரு நீக்கம், ஒரு ஓ (n), செயல்பாடு நிறைவு
நாம் நீக்குதல் n முதல் மற்றும், இந்த ஒரு ஓ (n ^ 2) குலைப்பதை வழிவகுக்கிறது.
சரி. அதனால் நல்ல துவக்கம். நல்ல துவக்கம்.
>> மற்றொரு கருத்து, னத் கலக்கு என்று ஏதாவது பயன்படுத்த வேண்டும்
அல்லது ஃபிஷர்-யேட்ஸ் குலைப்பதை.
அது உண்மையில் ஒரு நேரியல் நேரம் குலைப்பதை தான்.
மற்றும் யோசனை மிகவும் ஒத்ததாக இருக்கிறது.
மீண்டும், நாம், நம் உள்ளீடு வரிசை உள்ளது
ஆனால் அதற்கு பதிலாக நம் உள்ளீடு / வெளியீடு இரண்டு அணிகளை பயன்படுத்தி,
நாம், நமது மாற்றி மாற்றி கலக்கப்பட்டு பகுதியை கண்காணிப்பதற்கு அணி முதல் பகுதியை பயன்படுத்த
நாம் கண்காணிக்க, மற்றும் நாம் unshuffled பகுதி எங்கள் அணியின் மற்ற விட்டு.
எனவே இங்கே நான் சொல்லுகிறேன். நாம் தொடங்குகின்றன - நாம் ஒரு நான் தேர்வு,
0 முதல் 20 வரிசையை.
நமது தற்போதைய சுட்டிக்காட்டி முதல் குறியீட்டு சுட்டி காட்டியது.
நாம் சில நான் இங்கே தேர்வு
இப்போது நாம் பரிமாறிக்கொள்ளலாம்.
இந்த 5 மற்றும் இந்த 4 என்று நீங்கள்
இதன் விளைவாக வரிசை இங்கே 5 இங்கே மற்றும் 4 சாப்பிடும்.
இப்போது நாம் இங்கே ஒரு மார்க்கர் கவனிக்க.
இடது எல்லாம், மாற்றி மாற்றி கலக்கப்பட்டு
வலது எல்லாவற்றையும் unshuffled.
இப்போது நாம் செயல்முறை மீண்டும் முடியாது.
நாம் இப்போது 1 மற்றும் 20 ஆகியவற்றுக்கு இடையே ஒரு சீரற்ற குறியீட்டு தேர்வு.
அதனால் நான் இங்கே நமது புதிய நினைக்கிறேன்.
இப்போது நாம் இங்கே நமது தற்போதைய புதிய நிலையில் இந்த நான் பரிமாறிக்கொள்ளலாம்.
எனவே நாம் ஒரு இப்படி முன்னும் பின்னுமாக மாற்றம்.
எனக்கு அது இன்னும் உறுதியான செய்ய குறியீடு கொண்டு வரவும் விட.
நாம் நான் நம்முடைய தேர்வு தொடங்க -
நான் 0 சமமானதாக நாம் தொடங்க, நாம் ஒரு சீரற்ற இடம் j தேர்வு
வரிசைக்கு unshuffled பகுதியில், நான் n-1.
நான் இங்கே இருக்கிறேன் என்றால், இங்கே மற்றும் வரிசை மற்ற இடையே ஒரு சீரற்ற குறியீட்டு தேர்வு
நாம் பரிமாறிக்கொள்ளலாம்.
இந்த குலைப்பதை உங்கள் வரிசை தேவையான அனைத்து குறியீடு உள்ளது.
எந்த கேள்விகள்?
>> சரி, ஒரு கேள்வி தேவை, ஏன் இந்த சரியான உள்ளது?
ஏன் ஒவ்வொரு வரிசைமாற்ற சமமாக உள்ளது?
நான், இந்த ஆதாரம் மூலம் போக மாட்டேன்
ஆனால் கணினி அறிவியல் பல பிரச்சினைகள் தூண்டல் மூலம் நிரூபிக்கப்பட்டுள்ளது.
எப்படி பல தூண்டல் தெரிந்திருந்தால்?
சரி. Cool.
எனவே, எளிய அறிமுக இந்த வழிமுறையை சரியான நிரூபிக்க முடியும்
உங்கள் அறிமுக கருதுகோள் என்று அங்கு, என
என் குலைப்பதை ஒவ்வொரு வரிசைமாற்ற சமமாக வாய்ப்பு கொடுக்கிறது
வரை முதல் நான் உறுப்புகளை.
இப்போது, நான் + 1 கருதுகின்றனர்.
நாம் நமது குறியீட்டு j இடமாற்றம் தேர்வு மூலம்,
, மற்றும் நீங்கள் விவரங்களை வேலை - இந்த வழிவகுக்கிறது
இந்த வழிமுறை கொடுக்கிறது ஏன் குறைந்தது ஒரு முழு ஆதாரம்
சமமான வாய்ப்பு நிகழ்தகவு ஒவ்வொரு வரிசைமாற்ற.
>> சரி, அடுத்த பிரச்சனை.
எனவே ", எதிர்மறை, பூஜ்ஜியம், நேர் முழு எண்கள் ஒரு வரிசை, கொடுக்கப்பட்ட
அதிகபட்ச தொகையை கணக்கிட்டு ஒரு செயல்பாடு எழுத
உள்ளீடு வரிசைக்கு எந்த continueous subarray வேண்டும். "
இங்கே ஒரு எடுத்துக்காட்டாக, அனைத்து எண்கள் நேர்மறை எங்கே வழக்கில், தான்
பின்னர் தற்போது சிறந்த தேர்வு முழு வரிசை எடுத்து உள்ளது.
1, 2, 3, 4, 10 சமமாக.
நீங்கள் அங்கு சில எதிர்மறைகளை போது,
இந்த வழக்கில் நாங்கள் தான் முதல் இரண்டு வேண்டும்
-1 மற்றும் / அல்லது -3 தேர்வு எங்கள் கூட்டுத்தொகையாக கீழே கொண்டுவரும் என்பதால்.
சில நேரங்களில் நாம் வரிசை மத்தியில் தொடங்க வேண்டும்.
சில நேரங்களில் நாம் ஒன்றுமே தேர்வு செய்ய வேண்டும்; இது எதையும் எடுக்க சிறந்ததாகும்.
மற்றும் சில நேரங்களில் அது, இலையுதிர் எடுத்து நல்லது
அதை பிறகு தான் சூப்பர் பெரிய காரணம். எந்த கருத்துக்கள் மிகவும்?
(மாணவர், புரிந்து) >> சரி.
நான் -1 வேண்டாம் என்று நினைக்கிறேன்.
பின்னர் அல்லது நான் 1000 மற்றும் 20,000, தேர்வு
அல்லது நான் 3 பில்லியன் தேர்வு.
நல்ல, சிறந்த தேர்வாக அனைத்து எண்களை எடுத்து உள்ளது.
இந்த -1, எதிர்மறை இருந்தும்,
முழு தொகையை நான் -1 கொள்ள முடியவில்லை விட.
நான் முன்னர் குறிப்பிட்ட குறிப்புகள் ஒரு தெளிவாக வெளிப்படையாக கூற வேண்டும்
முதல் மற்றும் முரட்டு தீர்வு.
இந்த பிரச்சனையில் முரட்டு தீர்வு என்ன? அப்படியா?
[ஜேன்] சரி, நான் முரட்டு தீர்வு என்று
அனைத்து சேர்க்கைகள் (புரிந்து) வரை சேர்க்க வேண்டும்.
[யு] சரி. அதனால் ஜேன் யோசனை ஒவ்வொரு சாத்தியமான எடுத்து உள்ளது -
நான் paraphrasing நான் - ஒவ்வொரு சாத்தியமான தொடர் subarray எடுத்து உள்ளது,
அதன் தொகை கணக்கீடு, மற்றும் அனைத்து தொடர் subarrays அதிகபட்ச எடுத்து.
என்ன தனிப்பட்ட என் உள்ளீடு வரிசையில் ஒரு subarray அடையாளம்?
நான் என்ன இரண்டு விஷயங்கள் வேண்டும், போன்ற? அப்படியா?
(மாணவர், புரிந்து) >> வலது.
ஒரு குறைந்த குறியீட்டு மற்றும் ஒரு மேல் வரம்பையே குறியீட்டு மீது கட்டப்படுகிறது
தனிப்பட்ட ஒரு தொடர்ச்சியான subarray தீர்மானிக்கிறது.
[பெண் மாணவர்] நாம் அது தனிப்பட்ட எண்கள் ஒரு வரிசையில் தான் மதிப்பீடு என்ன?
[யு] இல்லை அவள் கேள்விக்கு எனவே, நாங்கள் எங்கள் அணி அனுமானித்து -
எங்கள் அணி அனைத்து தனிப்பட்ட எண்கள், மற்றும் பதில் இல்லை.
>> நாம் நம் முரட்டு தீர்வு, தொடக்கத்தில் / முடிவில் குறியீடுகள் பயன்படுத்தினால்
தனிப்பட்ட எமது தொடர்ச்சியான subarray தீர்மானிக்கிறது.
நாம் அனைத்து தொடக்க உள்ளீடுகளுக்கு கூறு என்றால்,
மற்றும் அனைத்து இறுதியில் உள்ளீடுகளுக்கு> அல்லது = தொடங்க, மற்றும் <n க்கு
நீங்கள் தொகை கணக்கீடு, பின்னர் நாம் இதுவரை பார்த்த அதிகபட்ச தொகையை எடுத்து.
இந்த தெளிவாக உள்ளது?
இந்த தீர்வு பெரிய ஓ என்ன?
Timewise.
மிக ^ 2 n.
, நாம் 0 இருந்து n க்கு கூறு என்பதை கவனத்தில்
அதனால் லூப் தான்.
நாம் லூப், கிட்டத்தட்ட தொடக்கத்தில் இருந்து முடிவு வரை மீண்டும் இன்னொரு கூறு.
இப்போது, அந்த நேரத்தில், நாம், ஒவ்வொரு நுழைவு வரை தொகையிடும் வேண்டும்
அதனால் லூப் மற்றொரு. எனவே நாங்கள் மூன்று சுழல்கள் ஒரு காக்கப்பட்ட, n ^ 3 வேண்டும்.
சரி. இந்த தொடக்க புள்ளியாக செல்கிறது.
எங்கள் தீர்வு n ^ 3 விட மோசமாக உள்ளது.
அனைவரும் முரட்டு தீர்வு புரிந்து?
>> சரி. ஒரு நல்ல தீர்வு டைனமிக் நிரலாக்க என்று ஒரு யோசனை பயன்படுத்துகிறது.
நீங்கள் CS124 எடுத்து இருந்தால், அது, நெறிமுறைகள் மற்றும் தரவு கட்டமைப்புகள் இல்லை
இந்த தொழில்நுட்பம் மிகவும் பழக்கமான மாறும்.
மற்றும் யோசனை, முதல் சிறிய பிரச்சினைகளுக்கு தீர்வுகளை கட்டமைக்க முயற்சி.
தொடக்க மற்றும் முடிவு: இது நான் என்ன, நாம் தற்போது இரண்டு விஷயங்களை பற்றி கவலைப்பட வேண்டும்.
அந்த எரிச்சலூட்டும் தான். நாம் அந்த அளவுருக்கள் ஒரு விடுபட முடியும் என்றால் என்ன?
நாங்கள் எங்கள் உண்மையான பிரச்சினை கொடுக்க, - ஒரு யோசனை உள்ளது
ஒரு வரம்பில் எந்த subarray அதிகபட்ச தொகை [ஓ, n-1] காணலாம்.
இப்போது நாம், நமது தற்போதைய குறியீட்டு நான், நாம் என்று ஒரு புதிய subproblem, வேண்டும்
நாம் அங்கு முடிவுக்கு வேண்டும் என்று. எங்கள் subarray தற்போதைய அட்டவணை இறுதி வேண்டும்.
மீதமுள்ள பிரச்சனை எனவே, அங்கு நாங்கள் எங்கள் subarray தொடங்க வேண்டும்?
இந்த உணர்வு ஏற்படுத்தும்? சரி.
அதனால் நான் இந்த வரை குறியாக்கம், என்ன அர்த்தம் பாருங்கள் நாம்.
Codirectory உள்ள, subarray என்று ஒரு திட்டத்தை, அங்கு
இது, பொருட்களை எண்ணிக்கை ஆகும்
அது என் மாற்றி மாற்றி கலக்கப்பட்டு பட்டியலில் அதிகபட்ச subarray தொகையை கொடுக்கிறது.
இந்த வழக்கில், எங்கள் அதிகபட்ச subarray 3.
என்று மட்டும் 2 மற்றும் 1 பயன்படுத்தி எடுக்கப்பட்ட.
அதை மீண்டும் இயக்க வேண்டும். இது 3 தான்.
ஆனால் இந்த நேரத்தில், நாம் 3 கிடைத்தது எப்படி கவனிக்க.
நாம் எடுத்து - நாம் வெறும் 3 தன்னை எடுத்து
அது இருபுறமும் எதிர்மறைகளை சூழப்பட்ட ஏனெனில்,
ஒரு தொகை <3 கொண்டுவரும் எந்த.
10 பொருட்கள் இயங்க அனுமதிக்க.
இது 7 தான் இந்த நேரத்தில், நாம் முன்னணி 3 மற்றும் 4 எடுத்து.
இந்த முறை 8, நாங்கள் 1, 4 மற்றும் 3 எடுத்து அந்த பெற.
நீ எப்படி ஒரு உள்ளுணர்வு கொடுக்க நாங்கள் இந்த மாற்றம் பிரச்சனையை தீர்க்க முடியும்,
இந்த subarray பாருங்கள் நாம்.
இந்த உள்ளீடு வரிசை கொடுக்கப்பட்ட, மற்றும் நாம் பதில் 8 தெரியும்.
நாம் 1, 4, மற்றும் 3 எடுத்து.
ஆனால் நாம் உண்மையில் அந்த பதில் கிடைத்தது எப்படி இருக்கும் என்று.
அது இந்த குறியீடுகள் ஒவ்வொரு மணிக்கு முடிந்தது என்று அதிகபட்ச subarray பார்க்கிறேன்.
முதல் நிலை முடிவுக்கு கொண்டுவரப்பட வேண்டும் என்று அதிகபட்ச subarray என்ன?
[மாணவர்] ஜீரோ. >> ஜீரோ. நான் -5 எடுத்து கொள்ள கூடாது.
இங்கே அது அதே 0 இருக்க போகிறது. அப்படியா?
(மாணவர், புரிந்து)
[யு] ஓ, மன்னிக்கவும், இது ஒரு -3 உள்ளது.
இந்த ஒரு 2 அதனால், இந்த ஒரு -3 உள்ளது.
சரி. எனவே -4, அந்த நிலையை முடிவுக்கு அதிகபட்ச subarray என்ன
-4 நேரத்தில் எங்கே? பூஜ்யம்.
ஒரு? 1, 5, 8.
இப்போது, நான் -2 நேரத்தில் எங்கே இடத்தில் முடிவுக்கு வேண்டும்.
எனவே 6, 5, 7, மற்றும் கடைசி ஒரு 4.
இந்த என் உள்ளீடுகளை என்று தெரிந்தும்
நான் இந்த குறியீடுகள் ஒவ்வொரு உள்ள முடிவுக்கு வேண்டும், அங்கு மாற்றினர் சிக்கல்,
பிறகு என் இறுதி பதில் தான், முழுவதும் ஒரு ஸ்வீப் எடுத்து
மற்றும் அதிகபட்ச எடுத்து.
இந்த வழக்கில் அது 8 தான்.
இந்த, அதிகபட்ச subarray இந்த குறியீட்டு முடிவடைகிறது என்பதை குறிக்கிறது
அது முன்னர் எங்கோ தொடங்கியது.
அனைவருக்கும் இந்த மாற்றம் subarray புரிந்து?
>> சரி. சரி, இந்த தொடர் கண்டுபிடிக்க வேண்டும்.
இது தான் முதல் சில உள்ளீடுகளை கருத்தில் கொள்வோம்.
இங்கு இது, 8 0, 0, 0, 1, 5 இருந்தது.
பின்னர் அங்கு ஒரு -2, அந்த 6 அதை கொண்டு.
நான் நிலையில் நுழைவு அழைப்பு அதனால் நான் subproblem (i)
எப்படி நான் ஒரு முந்தைய subproblem பதில் பயன்படுத்தலாம்
இந்த subproblem பதில்?
நான் பார்த்தால், இந்த நுழைவு, கூறலாம்.
எப்படி நான் பார்த்து பதில் 6 கணக்கிட முடியாது
இந்த வரிசையில் இந்த வரிசையில் முந்தைய subproblems பதில்களை கலவையை? ஆமாம்?
[பெண் மாணவர்] நீங்கள் பெருக்கத்தின் வரிசை எடுத்து
நிலையில் அதை முன், 8 ஆக
பின்னர் தற்போதைய subproblem சேர்க்க.
[யு], தனது பரிந்துரையை இந்த இரண்டு எண்கள் பார்க்க தான்
இந்த எண்ணிக்கை மேலும் இந்த எண்.
இந்த 8 subproblem பதில் (- 1 நான்) குறிக்கிறது.
மற்றும் என் உள்ளீடு வரிசை ஏ அழைப்பு விடு
நிலையை நான் முடிவடைகிறது என்று ஒரு அதிகபட்ச subarray கண்டுபிடிக்க வேண்டும்,
நான் இரண்டு தேர்வுகள் உள்ளன: நான் ஒன்று subarray தொடரலாம்
முந்தைய சுட்டு மணிக்கு முடிந்தது, அல்லது ஒரு புதிய அணியை தொடங்கும்.
நான், முந்தைய குறியீட்டு மணிக்கு தொடங்கியது என்று subarray தொடர்ந்து இருந்தால்
நான் சாதிக்க முடியும் அதிகபட்ச தொகை முந்தைய subproblem பதில் இல்லை
அத்துடன் தற்போதைய வரிசை இடுகை.
ஆனால், நான் கூட, ஒரு புதிய subarray துவங்கும் தேர்வு
இதில் கூட்டுத்தொகையாக 0 ஆகும்.
1, பிளஸ் தற்போதைய வரிசை இடுகை - அதனால் பதில் 0 அதிகபட்சம், subproblem நான் தான்.
இந்த மீண்டும் பயன்?
எங்கள் மீண்டும், நாம் தான் கண்டுபிடிக்கப்பட்டது என, subproblem நான் இல்லை
முந்தைய subproblem அதிகபட்ச மற்றும் என் தற்போதைய வரிசை நுழைவு சமமாக இருக்கும்
இது, முந்தைய subarray தொடர்ந்து பொருள்
அல்லது 0, என் தற்போதைய குறியீட்டு ஒரு புதிய subarray தொடங்கும்.
ஒருமுறை எங்கள் இறுதி பதில் பின்னர், தீர்வுகள் இந்த அட்டவணை இல்லாதபோது,
வெறும் subproblem வரிசை முழுவதும் ஒரு நேர்கோட்டு ஸ்வீப் செய்ய
மற்றும் அதிகபட்ச எடுத்து.
இந்த நான் என்ன சொன்னேன் என்று ஒரு சரியான நடைமுறை ஆகும்.
நாம் ஒரு புதிய subproblem வரிசை, subproblems உருவாக்க.
முதல் இடுகை 0 அல்லது முதல் இடுகை, அந்த இரண்டு அதிகபட்ச ஒன்று உள்ளது.
மற்றும் subproblems எஞ்சிய
நாம் தான் கண்டுபிடிக்கப்பட்டது சரியான மீண்டும் பயன்படுத்த.
இப்போது நாங்கள் எங்கள் subproblems அணியின் அதிகபட்ச கணக்கிட, மற்றும் நம் இறுதி பதில் தான்.
>> எனவே எவ்வளவு இடத்தை நாம் இந்த வழிமுறையை பயன்படுத்தி?
நீங்கள் மட்டும் CS50 எடுத்து இருந்தால், நீங்கள் மிகவும் இடத்தை பற்றி.
நன்றாக, கவனிக்க ஒன்று நான் அளவு n இங்கு malloc என்று அழைத்தது.
என்று நீங்கள் என்ன ஆலோசனை?
இந்த வழிமுறை நேரான இடத்தை பயன்படுத்துகிறது.
நாம் சிறப்பாக செய்ய முடியும்?
நீங்கள் இறுதி பதில் கணக்கிட தேவையற்ற என்பதை நீங்கள் கவனிக்க வேண்டும் என்று ஏதாவது இருக்கிறதா?
நான் நினைக்கிறேன் ஒரு நல்ல கேள்வி இது, என்ன தகவல்
நாம் இறுதியில் அனைத்து வழிகளிலும் செயல்படுத்த தேவையில்லை?
இப்போது, நாம் இந்த இரண்டு வரிகளை பாருங்கள் என்றால்,
நாம் மட்டுமே, முந்தைய subproblem பற்றி கவலை
நாம் மட்டுமே நாம் எப்போதும் இதுவரை பார்த்த அதிகபட்ச அக்கறை.
நம் இறுதி பதில் கணக்கிடுவதற்கு, நாம் முழு வரிசையில் தேவையில்லை.
நாம் கடந்த பல, கடந்த இரண்டு எண்கள் மட்டுமே தேவை.
அதிகபட்சம் subproblem வரிசை, மற்றும் கடந்த பல கடைசியாக எண்.
எனவே, உண்மையில், நாம் இந்த சுழல்கள் உருக
மேலும் ஒருபடி இடத்தை தொடர்ந்து விண்வெளி சென்று.
தற்போதைய தொகை இதுவரை, இங்கே, subproblem, எங்கள் subproblem வரிசை பங்கு மாற்றப்படும்.
எனவே தற்போதைய தொகை, இதுவரை, முந்தைய subproblem பதில் இல்லை.
அந்த தொகை, இதுவரை, எங்கள் அதிகபட்சம் என்ற நடைபெறுகிறது.
நாம் சேர்ந்து போகலாம் என்று நாம் அதிகபட்ச கணக்கிட.
அதனால் நாம், நிலையான இடத்தில் நேரியல் வெளி செல்ல
நாம் நம் subarray பிரச்சினை ஒரு நேர்கோட்டு தீர்வு வேண்டும்.
>> கேள்விகளை இந்த வகையான ஒரு பேட்டியில் போது வருவீர்கள்.
சிக்கலான நேரத்தை என்ன; விண்வெளி சிக்கல் என்ன?
நீங்கள் நன்றாக செய்ய முடியும்? சுற்றி வைக்க தேவையற்ற என்று விஷயங்கள் உள்ளன?
நான் உங்கள் சொந்த எடுக்க வேண்டும் என்று ஆய்வுகள் முன்னிலைப்படுத்த இதை
இந்த பிரச்சினைகள் மூலம் உழைக்கும் என.
எப்போதும் "நான் நன்றாக செய்ய முடியுமா?", உங்களை கேட்கலாம்
உண்மையில், நாம் இதை விட சிறப்பாக செய்ய முடியும்?
ஒரு தந்திரம் கேள்வி வகையான. நீங்கள் வேண்டும், ஏனெனில் நீங்கள், முடியாது
குறைந்தது பிரச்சனை உள்ளீடு வாசிக்க.
நீங்கள் வேண்டும் என்று உண்மையில் குறைந்தபட்சம் பிரச்சனை உள்ளீடு படிக்க மிகவும்
நீங்கள், நேரியல் நேரம் விட முடியாது என்று அர்த்தம்
நீங்கள் நிலையான இடத்தை விட முடியாது.
இந்த, உண்மையில், இந்த பிரச்சினைக்கு தீர்வு.
கேள்விகள்? சரி.
>> பங்கு சந்தை பிரச்சனை:
"நேர்மறை, பூஜ்யம் அல்லது எதிர்மறையான n இன்டீஜர்கள், ஒரு வரிசை நிலையில்,
என்று, n நாட்களில் ஒரு பங்கின் விலை பிரதிநிதித்துவம்
நீங்கள் செய்ய முடியும் அதிகபட்ச லாபத்தை கணக்கிட ஒரு செயல்பாடு எழுத
இந்த n நாட்களுக்குள் சரியாக 1 பங்கு வாங்க, விற்க என்று கொடுக்கப்பட்ட. "
முக்கியமாக, நாம், குறைந்த விலைக்கு வாங்கி அதிக விலைக்கு விற்க வேண்டும்.
மற்றும் நாம் உருவாக்க முடியும் சிறந்த இலாப கண்டுபிடிக்க வேண்டும்.
என் நுனி செல்கிறேன், என்ன உடனடியாக தெளிவான, எளிய பதில், ஆனால் அது மெதுவாக தான்?
ஆமாம்? (மாணவர், புரிந்து) >> ஆம்.
>> எனவே நீங்கள் தான் என்றாலும் போய் பங்கு விலைகள் பார்ப்பார்கள்
அந்த நேரத்தில் ஒவ்வொரு புள்ளி, (புரிந்து).
[யு] சரி, அவளை தீர்வு - கணினி தனது பரிந்துரை
குறைந்த மற்றும் அதிக கணக்கிடும் அவசியம் வேலை இல்லை
அதிக குறைந்த முன் நிகழலாம் என்பதால்.
எனவே இந்த பிரச்சினைக்கு முரட்டு தீர்வு என்ன?
நான் தனிப்பட்ட நான் செய்ய இலாப தீர்மானிக்க வேண்டும் என்று இரண்டு விஷயங்கள் என்ன? சரி.
முரட்டு தீர்வு - ஓ, அதனால், ஜார்ஜ் பரிந்துரை நாம் இரண்டு நாட்கள் தேவை இல்லை
தனிப்பட்ட அந்த இரண்டு நாட்கள் இலாப தீர்மானிக்க.
எனவே, வாங்க / விற்க போல், ஒவ்வொரு ஜோடி கணக்கிட
எதிர்மறை அல்லது நேர்மறை அல்லது பூஜ்ஜியம் என்று இலாப, கணக்கிட.
நாம் நாட்களில் அனைத்து ஜோடிகள் மீது தேடி பின்னர் செய்யும் அதிகபட்ச லாபத்தை கணக்கிட.
என்று நம் இறுதி பதில் இருக்கும்.
அந்த தீர்வு இல்லை என்பதால், ஓ (n ^ 2) இருக்கும் n இரண்டு ஜோடிகள் தேர்வு -
நீங்கள் இறுதி நாட்களில் மத்தியில் தேர்வு செய்யலாம் என்று நாட்கள்.
சரி, நான் இங்கே முரட்டு தீர்வு மேல் செல்ல போவதில்லை.
நான் ஒரு n log n தீர்வு இல்லை என்று சொல்ல போகிறேன்.
நீங்கள் தற்போது n log n என்று என்ன வழிமுறை தெரியுமா?
இது ஒரு தந்திரம் பிரச்சினை அல்ல.
>> சேர்ப்பு வரிசையாக்கம். ஒன்றாக்க வகையான, n log n ஆகும்
உண்மையில், இந்த சிக்கலை தீர்க்க ஒரு வழி பயன்படுத்த வேண்டும்
என்று யோசனை ஒரு பிணைப்பு வகையான வகையான, பொதுவாக, பிரித்து வெற்றி.
பின்வருமாறு மற்றும் யோசனை.
நீங்கள் சிறந்த வாங்க கணக்கிட / இடது பாதியில் ஜோடி விற்க வேண்டும்.
நீங்கள் இரண்டு நாட்கள் முதல், n, செய்யலாம் சிறந்த இலாபம் தேட.
பிறகு, சிறந்த வாங்க oompute / சரி பாதி மீது ஜோடி விற்க வேண்டும்
இரண்டு நாட்களில் மிகவும் கடைசி n.
இப்போது கேள்வி எப்படி நாம் மீண்டும் ஒன்றாக இந்த தீர்வுகள் ஒன்றாக்க வேண்டாம், இது?
ஆமாம்? (மாணவர், புரிந்து)
சரி >>. என்னை ஒரு படம் வரைய வேண்டும்.
ஆமாம்? (ஜார்ஜ், புரிந்து)
சரியாக >>. ஜார்ஜ் தீர்வு சரியாக இருக்கும்.
அவரது ஆலோசனையை அதனால், முதல், சிறந்த வாங்கி / விற்கும் ஜோடி கணக்கிட
மற்றும் இடது பகுதியில் ஏற்படும் என்று, எனவே இடது, இடது என அழைக்கிறேன்.
சிறந்த சரி பாதி ஏற்படுகிறது என்று ஜோடி வாங்க / விற்க.
நாம் இந்த இரண்டு எண்கள் ஒப்பிடுகையில் ஆனால், நாங்கள் வழக்கு காணவில்லை
நாம் இங்கே வாங்க மற்றும் வலது பகுதியில் எங்காவது விற்க வேண்டும்.
நாம் இடது பாதியில் வாங்க, வலது பாதி விற்க.
இரண்டு பகுதிகளாக பரவியுள்ள சிறந்த வாங்கி / விற்கும் ஜோடி கணக்கிட சிறந்த வழி
இங்கே குறைந்தபட்ச கணக்கிட மற்றும் இங்கே அதிகபட்ச கணக்கிட வேண்டும்
அவர்களது வேறுபாடு எடுக்க.
வாங்க / விற்க ஜோடி மட்டும் இங்கே ஏற்படும் இரண்டு வழக்குகள் எனவே,
இங்கே தான், அல்லது இரண்டு பகுதிகளாக இந்த மூன்று எண்களை வரையறுக்கப்படுகிறது.
, மீண்டும் ஒன்றாக நம் தீர்வுகளை இணைவதற்கு எங்கள் வழிமுறை மிகவும்
நாம் சிறந்த வாங்கி / விற்கும் ஜோடி கணக்கிட வேண்டும்
நாம் இடது பாதி மீது வாங்க மற்றும் வலது பாதி மீது விற்க வேண்டும்.
அதை செய்ய சிறந்த வழி, முதல் பாதி மிகவும் குறைந்த விலை கணக்கிட வேண்டும்
உயர்ந்த வலது பாதி விலை, மற்றும் அவர்களது வித்தியாசத்தை எடுத்து.
இதனால் மூன்று இலாபங்கள், இந்த மூன்று எண்கள், நீங்கள், மூன்று அதிகபட்ச எடுத்து
என்று நீங்கள் இந்த முதல் மற்றும் இறுதி நாட்களில் செய்யலாம் சிறந்த லாபம்.
இங்கே முக்கியமான வரிகளை சிவப்பு உள்ளன.
இந்த இடது பாதியில் பதில் கணக்கிட ஒரு சுழல்நிலை அழைப்பு.
இது சரியான பகுதியில் பதில் கணக்கிட ஒரு சுழல்நிலை அழைப்பு.
இந்த இரண்டு சுழல்கள் ஒரு முறையே, இடது மற்றும் வலது பாதி மீது நிமிடம் மற்றும் அதிகபட்சம் கணக்கிட.
இப்போது நான், இரண்டு பகுதிகளாக பரவியுள்ள இலாப கணக்கிட
இறுதி பதில் இந்த மூன்று அதிகபட்ச உள்ளது.
சரி.
>> எனவே, நிச்சயமாக, நாம் ஒரு வழிமுறை உண்டு, ஆனால் பெரிய கேள்வி
இந்த சிக்கலான நேரத்தை என்ன?
நான் ஒன்றிணைப்பு வகையான குறிப்பிட்டுள்ளார் காரணம் இந்த வடிவம் பதில் பிரித்து என்று
இரண்டு பின் மீண்டும் ஒன்றாக நம் தீர்வுகளை இணைத்தல்
சரியாக ஒன்றிணைப்பு மாதிரி வடிவம்.
என்னை கால மூலம் செல்லலாம்.
நாம் நடவடிக்கைகளை எண்ணிக்கை இருக்கும் ஒரு செயல்பாடு t (n) வரையறுக்கப்பட்ட என்றால்
n நாட்கள்,
எங்கள் இரண்டு சுழல்நிலை அழைப்பு
ஒவ்வொரு t (n / 2), செலவு செய்ய போகிறாய்
இந்த அழைப்புகள் இரண்டு உள்ளது.
இப்போது நான், இடது பாதி குறைந்தபட்ச கணக்கிட வேண்டும்
நான் n / 2 நேரம், மற்றும் வலது பாதி அதிகபட்ச செய்ய முடியும்.
எனவே இந்த n.
பின்னர் சில நிலையான வேலை பிளஸ்.
இந்த மறுநிகழ்வு சமன்பாடு
சரியாக ஒன்றிணைப்பு வகையான தொடர் சமன்பாடு.
நாம் அனைத்து ஒன்றிணைப்பு வகையான n log n நேரம் என்று எனக்கு தெரியும்.
எனவே, எங்கள் வழிமுறையானது பதிவு n நேரம் n.
இந்த மறு செய்கை பயன்?
இந்த ஒரு சிறிய முறையை:
டி (n) அதிகபட்ச லாபத்தை கணக்கிட நடவடிக்கைகளை எண்ணிக்கை
n நாட்களில் படிப்படியாக.
நாம் சுழல்நிலை அழைப்புகள் பிரிந்து வழி
, முதல் n / 2 நாட்களில் எங்கள் தீர்வு கோரி உள்ளது
அதனால் ஒரு அழைப்பு, தான்
மற்றும் நாம் இரண்டாவது பாதி மீண்டும் அழைப்பு.
அதனால் இரண்டு அழைப்புகள் தான்.
பின்னர் நாம், நாம் நேரியல் நேரம் செய்ய முடியும், இடது பாதி ஒரு குறைந்தபட்ச கண்டறிய
நாம் நேரியல் நேரம் செய்ய இது சரியான அரை அதிகபட்ச கண்டுபிடிக்க.
எனவே n / 2 + n / 2 தான் n ஆகும்.
நாம் கணித செய்து போல் சில நிலையான வேலை, இல்லை.
இந்த மறுநிகழ்வு சமன்பாடு சரியாக ஒன்றிணைப்பு வகையான தொடர் சமன்பாடு.
எனவே, எங்கள் குலைப்பதை வழிமுறை உள்ளது n n log.
எனவே எவ்வளவு இடத்தை நாம் பயன்படுத்தும்?
இந்த குறியீடு திரும்பி செல்லலாம்.
>> ஒரு நல்ல கேள்வி, எப்படி பல அடுக்கு சட்டங்களை நாம் எப்போதும் எந்த நேரத்திலும் இல்லை?
நாம் மறுநிகழ்வு பயன்படுத்தி பின்னர்,
ஸ்டாக் பிரேம்கள் எண்ணிக்கை நம் விண்வெளி பயன்பாடு தீர்மானிக்கிறது.
அது n = 8 கருத்தில் கொள்வோம்.
நாம், 8 குலைப்பதை அழைப்பு
முதல் நான்கு உள்ளீடுகளை குலைப்பதை அழைப்பு அது,
இதில் முதல் இரண்டு உள்ளீடுகளை ஒரு கலக்கு அழைக்கும்.
எனவே எங்கள் ஸ்டாக் இல்லை - இந்த எங்கள் ஸ்டாக் இல்லை.
பின்னர் நாம், 1 ம் தேதி மீண்டும் குலைப்பதை அழைப்பு
மற்றும் அது நமது அடிப்படை வழக்கு என்ன ஆகும், எனவே நாம் உடனடியாக திரும்ப.
நாம் எப்போதும் இந்த பல அடுக்கு சட்டங்களை விட வேண்டும்?
இல்லை, நாம் ஒரு பிராத்தனை செய்ய ஒவ்வொரு முறையும் ஏனெனில்,
குலைப்பதை ஒரு சுழல்நிலை பிரார்த்தனையுடன்,
நாம் பாதி நம் அளவு பிரிக்க.
நாம் எப்போதும் எந்த நேரத்திலும் வேண்டும் ஸ்டேக் அதிக பட்ச எண்ணிக்கை மிகவும்
பதிவு n ஸ்டேக் பிரேம்கள் வரிசையில் உள்ளது.
ஒவ்வொரு ஸ்டாக் சட்டகமானது, நிலையான இடம்
இடத்தை எனவே மொத்த அளவு,
நாம் எப்போதும் பயன்படுத்த இடத்தை அதிகபட்ச அளவு ஓ (log n) இடைவெளி இருக்கிறது
அங்கு n நாட்கள் எண்ணிக்கை.
>> இப்போது, எப்போதும் உங்களை கேட்க, "நாங்கள் நன்றாக செய்ய முடியுமா?"
குறிப்பாக, நாம் ஏற்கனவே தீர்க்கப்பட நான் ஒரு பிரச்சனை இந்த குறைக்க முடியும்?
ஒரு குறிப்பை: நாம் இந்த முன் இரண்டு மற்ற பிரச்சினைகள் பற்றி, மற்றும் அது குலைப்பதை இருக்க போகிறது இல்லை.
நாம் அதிகபட்ச subarray பிரச்சனை இந்த பங்கு சந்தை பிரச்சனை மாற்ற முடியும்.
எப்படி இதை செய்ய முடியும்?
நீங்கள் ஒரு? எம்மி?
(எம்மி, புரிந்து)
[யு] சரியாக.
அதிகபட்ச subarray பிரச்சனை,
நாம் ஒரு தொடர் subarray ஒரு தொகை தேடுகிறீர்கள்.
மற்றும் பங்குகள் பிரச்சனை எம்மி ஆலோசனையும்,
மாற்றங்கள், அல்லது கழிமுக கருதுகின்றனர்.
இந்த ஒரு படம் தான் - இந்த ஒரு பங்கு விலை என்பது,
ஆனால் நாம் ஒவ்வொரு தொடர்ச்சியான நாள் வித்தியாசம் எடுத்து என்றால் -
எனவே அதிகபட்ச விலை, அதிகபட்ச லாபம் நாம் செய்ய முடியும் என்று பார்க்க
நாம் இங்கே வாங்க மற்றும் இங்கே விற்க இருக்கிறது.
ஆனால் அது தொடர்ந்து பார்த்து விட்டு - தான் subarray பிரச்சனை பார்க்க வேண்டும்.
எனவே இங்கே, நாம் செய்ய முடியும் - இங்கிருந்து இங்கே சென்று,
நாம் ஒரு நல்ல மாற்றம் வேண்டும், பின்னர் இங்கே இங்கே இருந்து நாம் ஒரு எதிர்மறை மாற்றம் வேண்டும்.
ஆனால் பின்னர், நாங்கள் ஒரு பெரிய நல்ல மாற்றம் இல்லை இங்கிருந்து இங்கே என்ன.
இந்த நாங்கள் எங்கள் இறுதி லாபம் கிடைக்கும் வரை தொகையிடும் வேண்டும் என்று மாற்றங்கள்.
நாம் இன்னும் எதிர்மறை மாற்றங்கள் இங்கே இல்லை.
எங்கள் அதிகபட்ச subarray பிரச்சினை நமது பங்கு சிக்கல் குறைக்கும் முக்கிய
நாட்கள் இடையே கழிமுக கருத்தில் கொள்ள வேண்டும்.
எனவே, கழிமுக என்று ஒரு புதிய அணியை உருவாக்க
, 0 முதல் இடுகை துவக்க
பின்னர் ஒவ்வொரு டெல்டா க்கு (நான்), வேறுபாடு இருக்கும் என்று நாம்
என் உள்ளீடு வரிசை (நான்), மற்றும் வரிசை (நான் - 1).
நாம் ஒரு அதிகபட்ச subarray எங்கள் வழக்கமான நடைமுறை அழைப்பு
ஒரு டெல்டா இன் வரிசையில் செல்லும்.
மற்றும் பெருமதிப்பு subarray நேரியல் நேரம், ஏனெனில்
இந்த குறைப்பு, இந்த டெல்டா வரிசை உருவாக்கும் இந்த செயல்முறை,
, மேலும் ஒருபடி நேரம்
பிறகு பங்குகள் இறுதி தீர்வு ஓ (n) வேலை மற்றும் ஓ (n) வேலை, இன்னும் ஓ (n) வேலை.
எனவே நாம் நமது பிரச்சனை ஒரு நேரியல் நேரம் தீர்வு வேண்டும்.
அனைவருக்கும் இந்த மாற்றத்தை புரிந்து?
>> நீங்கள் எப்போதும் இருக்க வேண்டும் என்று பொதுவாக, ஒரு நல்ல யோசனை
நீங்கள் காண்கிறீர்கள் என்று ஒரு புதிய சிக்கல் குறைக்க முயற்சி.
அது ஒரு பழைய சிக்கல் நன்கு தெரிகிறது என்றால்,
ஒரு பழைய பிரச்சனை அதை குறைக்கும் முயற்சி.
நீங்கள் பழைய பிரச்சனை பயன்படுத்தப்படும் என்று அனைத்து கருவிகள் பயன்படுத்த முடியும் என்றால்,
புதிய சிக்கலை தீர்க்க.
எனவே மடிக்க வேண்டும், தொழில்நுட்ப நேர்முக சவால்.
இந்த சிக்கல்கள் பெரும்பாலும் கடினமான பிரச்சினைகள் சில
நீங்கள், ஒரு பேட்டியில் பார்க்க என்று
நீங்கள் நான் மூடப்பட்டிருக்கும் என்று அனைத்து பிரச்சினைகள் புரியவில்லை என்றால், அது பரவாயில்லை.
இந்த சவாலான சிக்கல்கள் உள்ளன.
நடைமுறையில், நடைமுறையில், நடைமுறையில்.
நான் துண்டு பிரசுரம் பிரச்சினைகள் நிறைய கொடுத்து, அதனால் நிச்சயமாக அந்த பாருங்கள்.
உங்கள் நேர்முக நல்ல அதிர்ஷ்டம். என் வளங்கள், இந்த இணைப்பை இடப்பட்டவை
என் மூத்த நண்பர் ஒருவர், போலி தொழில்நுட்ப நேர்முக செய்ய முன்வந்தார்
நீங்கள் ஆர்வம் நீங்கள், மின்னஞ்சல் அந்த மின்னஞ்சல் முகவரியில் யோ வில்.
உங்களிடம் சில கேள்விகள் இருந்தால், நீங்கள் என்னை கேட்கலாம்.
நீங்கள் தொழில்நுட்ப நேர்முக தொடர்பான குறிப்பிட்ட கேள்விகள்
அல்லது நாம் இதுவரை பார்த்த எந்த பிரச்சினைகள்?
சரி. சரி, உங்கள் நேர்முக நல்ல அதிர்ஷ்டம்.
[CS50.TV]