[Powered by Google Translate] ஒருவேளை நீங்கள் ஒரு வேகமான அல்லது திறமையான வழிமுறை பற்றி பேச கேட்டிருக்கிறேன்
உங்கள் குறிப்பிட்ட பணியை இயக்கும் க்கு,
ஆனால் அது வேகமாக அல்லது செயல்திறன் மிக்கதாக ஒரு வழிமுறைக்கு சரியாக என்ன அர்த்தம்?
சரி, அது, உண்மையான நேரத்தில் ஒரு அளவீட்டு பற்றி பேசவில்லை
விநாடிகள் அல்லது நிமிடங்கள் போல.
இந்த ஏனென்றால் கணினி வன்பொருள்
மற்றும் மென்பொருள் கடுமையாக வேறுபடும்.
என் திட்டம், உன் விட மெதுவாக இயக்க வேண்டும்
நான், ஒரு பழைய கணினியில் அது இயங்கும் ஏனெனில்
அல்லது நான் ஒரு ஆன்லைன் வீடியோ விளையாட்டை வேண்டும் நடக்க காரணம்
அதே நேரத்தில், அது, என் நினைவு குவி வளைவு
அல்லது நான் வேறு மென்பொருள் மூலம் என் இயங்குவதாக
இது ஒரு குறைந்த அளவில் வேறுபட்டு இயந்திரம் தொடர்பு.
அது ஆப்பிள், ஆரஞ்சு ஒப்பிட்டு போல.
என் மெதுவாக கணினி இனி எடுக்கும் தான்
உன் ஒரு பதில் திரும்ப கொடுக்க விட
நீங்கள் இன்னும் திறமையான வழிமுறை இல்லை என்று அர்த்தம் இல்லை.
>> எனவே, நாங்கள் நேரடியாக திட்டங்கள் இயக்கநேரங்களுக்க்கு ஒப்பிட்டு முடியாது என்பதால்
விநாடிகள் அல்லது நிமிடங்கள்,
எப்படி நாம் 2 வெவ்வேறு வழிமுறைகள் ஒப்பிட்டு
அவர்களின் வன்பொருள் அல்லது மென்பொருள் சூழல்?
படித்தீர்வு திறன் அளவிடும் ஒரு சீரான முறையில் உருவாக்க,
கணினி விஞ்ஞானிகள் மற்றும் கணித சூழ்ச்சி
ஒரு திட்டத்தை அஸிம்டாடிக் சிக்கலான அளவிடும் கருத்துக்கள்
மற்றும் ஒரு குறியீடு 'பிக் Ohnotation' என்று
இந்த விளக்க.
சாதாரண வரையறை என்பது ஒரு சார்பு f (x)
கிராம் வரிசை (x) இயங்கும்
சில (x) மதிப்பு உள்ளது இருந்தால் x ₀ மற்றும்
சில மாறிலி, சி, எந்த
f (x) குறைவாக அல்லது சமமாக உள்ளது
நிலையான முறை கிராம் (x)
x ₀ விட அனைத்து x க்காக.
>> ஆனால் சாதாரண வரையறை விட்டு பயப்படாதே.
இந்த உண்மையில் கோட்பாட்டு அடிப்படையில் குறைந்த என்ன அர்த்தம்?
சரி, அது அடிப்படையில் பகுப்பாய்வு ஒரு வழி
ஒரு நிரல் இயக்க தொலைத்தொடுகோட்டு வளரும் எப்படி வேகமாக.
உங்கள் உள்ளீடுகள் அளவு முடிவிலியை நோக்கி அதிகரிக்கிறது என்று,, என்பது
சொன்னதை நீங்கள் அளவு 10 அணிவரிசை ஒப்பிடும்போது அளவு 1000 அணிவரிசை வரிசையாக்க.
உங்கள் திட்டத்தின் இயக்க எப்படி வளரும்?
எடுத்துக்காட்டாக, எழுத்துக்கள் எண்ணிக்கை எண்ணி கற்பனை
ஒரு சரம் இல் எளிய வழி
முழு சரம் வழியாக நடந்தே
கடிதம் மூலம் கடிதம் மற்றும் ஒவ்வொரு பாத்திரம் ஒரு இடத்திற்கு 1 சேர்க்கும்.
இந்த வழிமுறை நேரான நேரத்தில் இயக்க கூறப்படுகிறது
எழுத்துக்கள் எண்ணிக்கையை பொறுத்து,
சரம், 'n'.
சுருக்கமாக, அது O (n) இயங்கும்.
ஏன் இது?
சரி, இந்த அணுகுமுறையை பயன்படுத்தி, நேரம் தேவைப்படுகிறது
முழு சரம் பிரயாணம்
எழுத்துக்களின் எண்ணிக்கை சரிசமமாக உள்ளது.
20 சரத்தை உள்ள எழுத்துக்களின் எண்ணிக்கை எண்ணிக்கை
அதை எடுத்து இருமடங்கு நீண்ட நடக்கப்போகிறது
10 சரத்தை உள்ள எழுத்துக்களை எண்ணுவதற்கு,
நீங்கள் அனைத்து எழுத்துகள் இருக்க வேண்டும், ஏனெனில்
ஒவ்வொரு தன்மையை கவனிக்க நேரம் அதே அளவு ஆகும்.
நீங்கள் எழுத்துக்கள் எண்ணிக்கை அதிகரிக்கும், என
இயக்க உள்ளீடு நீளம் நேர்க்கோட்டுரீதியில் அதிகரிக்கும்.
>> நீங்கள் நேரியல் நேரம் முடிவு செய்தால் இப்போது, கற்பனை
ஓ (n), தான் வேகமாக போதும் உங்களுக்கு இல்லை?
ஒருவேளை நீங்கள், பெரும் சரங்களை சேமித்து
நீங்கள் அதை எடுத்து கூடுதல் நேரம் செலவிட முடியாது
ஒரு மூலம் ஒரு எண்ணி தங்கள் எழுத்துக்கள் அனைத்து தொடரவேண்டும்.
எனவே, நீங்கள் வேறு ஏதாவது முயற்சி முடிவு.
என்ன நீங்கள் ஏற்கனவே எழுத்துக்கள் எண்ணிக்கை சேமிக்க நடந்தால்
சரம் இல், ', லென்' என்று ஒரு மாறி, என்று
ஆரம்ப திட்டத்தில் மீது,
நீங்கள் கூட உங்கள் சரம் இல் முதல் எழுத்து சேமிக்கப்படும் முன்?
பின்னர், அனைத்து நீ, சரம் நீளம் கண்டுபிடிக்க இப்போது செய்ய வேண்டும் என்று
மாறி மதிப்பு என்னவென்று பாருங்கள்.
நீங்கள், எல்லா சரம் தன்னை பார்க்க வேண்டும் என்று
மற்றும் லென் போன்ற ஒரு மாறி மதிப்பு அணுகும் கருதப்படுகிறது
ஒரு தொலைத்தொடுகோட்டு மாறா நேரம் அறுவை சிகிச்சை,
அல்லது ஓ (1).
ஏன் இது? சரி, எந்த அறிகுறியும் சிக்கல் என்றால் என்ன ஞாபகம்.
எப்படி அளவில் இயக்க மாற்றம் இல்லை
உங்கள் உள்ளீடுகள் வளரும்?
>> நீங்கள் ஒரு பெரிய சரம் உள்ள எழுத்துக்களின் எண்ணிக்கை பெற முயற்சி என்று.
சரி, அது, நீங்கள் சரம் செய்ய எப்படி பெரிய விஷயமல்ல என்று
ஒரு மில்லியன் கதாபாத்திரங்கள் நீண்ட,
அனைத்து நீ, இந்த அணுகுமுறை கொண்ட சரம் இன் நீளம் கண்டுபிடிக்க செய்ய வேண்டும் என்று
, மாறி லென் மதிப்பு படிக்க வேண்டும்
இதில் நீங்கள் ஏற்கனவே.
என்று உள்ளீடு நீளம், நீங்கள் காண முயற்சிக்கும் சரம் நீளம்,
உங்கள் நிரலை இயக்கும் எப்படி வேகமாக அனைத்து பாதிக்காது.
உங்கள் திட்டம் இந்த பகுதி ஒரு சரத்தை சம அளவில் வேகமாக இயக்க வேண்டும்
ஒரு ஆயிரம்-சரத்தை,
இந்த திட்டத்தை தொடர்ந்து நேரத்தில் இயங்கும் என குறிப்பிடப்படுகிறது என்று ஏன் என்று
உள்ளீடு அளவை பொறுத்து.
>> நிச்சயமாக, ஒரு பின்னடைவாக உள்ளது.
நீங்கள் உங்கள் கணினியில் கூடுதல் நினைவக இடத்தை செலவிட
மாறி சேமித்து
அதை நீங்கள் எடுக்கும் கூடுதல் நேரம்
மாறி உண்மையான சேமிப்பு செய்ய,
ஆனால் புள்ளி இன்னும் உள்ளது,
உங்கள் சரம் எப்படி நீண்ட கண்டுபிடிப்பதில்
அனைத்து சரம் நீளம் நம்பி இல்லை.
எனவே, அது O (1) அல்லது நிலையான நேரத்தில் இயங்கும்.
இந்த நிச்சயமாக சொல்ல வேண்டும் இல்லை
உங்கள் குறியீடு, 1 படியில் இயங்கும்
ஆனால் எவ்வளவு பல நடவடிக்கைகளை அது,
இது உள்ளீடுகளின் அளவை மாற்ற முடியவில்லை எனில்,
இன்னும் நாம் ஓ (1) என பிரதிநிதித்துவப்படுத்தும் தொலைத்தொடுகோட்டு தொடர்ந்து தான்.
>> ஒருவேளை நீங்கள் யூகிக்க முடியும் என,
நெறிமுறைகள் அளவிட பல பெரிய ஓ இயக்கநேரங்களுக்க்கு உள்ளன.
ஓ (n) ² வழிமுறைகளை ஓ (n) வழிமுறைகளை விட தொலைத்தொடுகோட்டு மெதுவாக இருக்கும்.
தனிமங்களின் எண் (n) வளரும் என்று,, என்பது
இறுதியில் ஓ (n) ² வழிமுறைகளை இன்னும் நேரம் எடுக்கும்
ஓ (n) வழிமுறைகளை இயக்க விட.
இந்த ஓ (n) வழிமுறைகளை எப்போதும் வேகமாக ரன் அர்த்தம் இல்லை
ஓ (n) ² வழிமுறைகளை விட, அதே சூழலில்,
அதே வன்பொருளில்.
ஒருவேளை சிறிய உள்ளீடு அளவுகளுக்காக,
ஓ (n) ² வழிமுறை உண்மையில், வேகமாக வேலை செய்யலாம்
ஆனால், இறுதியில், உள்ளீடு அளவில் அதிகரிக்கிறது
முடிவிலியை நோக்கி, ஓ (n) ² வழிமுறைகளின் இயக்க
இறுதியில் ஓ (n) படிமுறையின் இயக்க மங்க செய்யும்.
எந்த இருபடி கணித செயல்பாடு போன்ற
இறுதியில் எந்த நேர்கோட்டு சார்பு முந்த வேண்டும்,
எவ்வளவு ஒரு தலை நேர்கோட்டு சார்பு தொடங்க எந்த விஷயம் ஆஃப் தொடங்குகிறது.
நீங்கள் தரவு பெரிய அளவு, உடன் வேலை என்றால்
ஓ இயக்க வழிமுறைகளை (n) ² நேரம் உண்மையில், உங்கள் திட்டம் மெதுவாக எழுந்து முடியும்
ஆனால் சிறிய உள்ளீடு அளவுகளுக்காக,
ஒருவேளை நீங்கள் கவனிக்க மாட்டேன்.
>> மற்றொரு அணுகுமுறை சிக்கல் உள்ளது
மடக்கை நேரம், O (log n).
விரைவில் இந்த இயங்கும் வழிமுறையின் ஒரு உதாரணம்
, செவ்வியல் இரும தேடல் வழிமுறையாகும்
தனிமங்களின் ஏற்கெனவே வரிசைப்படுத்தப்பட்ட பட்டியலில் ஒரு உறுப்பு கண்டறிவதற்கான.
>> நீங்கள் இரும தேடல் என்ன தெரியாது என்றால்,
நான் விரைவில் நீங்கள் அதை விளக்க வேண்டும்.
நாம் உங்களை எண் 3 தேடுகிறீர்கள் என்று
முழுஎண்களின் இந்த வரிசையில்.
அது அணியின் நடுத்தர உறுப்பு நோக்குகிறது
மற்றும் "நான் விட வேண்டும் உறுப்பு உள்ளது, சமமாக அல்லது இந்த குறைவான?", என்று கேட்கிறார்
அது பெரிய, சம இருந்தால். நீங்கள் உறுப்பு காணப்படவில்லை, மற்றும் நீங்கள் முடித்துவிட்டீர்கள்.
இது பெரிய இருந்தால், நீங்கள் உறுப்பு தெரியும்
, அணியின் வலது பக்க இருக்க வேண்டும்
நீங்கள் மட்டுமே, எதிர்காலத்தில் பார் முடியாது
இது சிறிய விஷயம் என்றால், அதை இடது புறம் இருக்க வேண்டும் என்று.
இந்த செயல்முறை பின் சிறிய அளவு வரிசை மீண்டும்
சரியான உறுப்பு காணப்படுகிறது வரை.
>> இந்த சக்தி வாய்ந்த வழிமுறையை ஒவ்வொரு அறுவை சிகிச்சை மூலம் பாதி வரிசை அளவு வெட்டி.
எனவே, அளவு 8 ஒரு வரிசைப்படுத்தப்பட்ட வரிசையில் ஒரு உறுப்பு கண்டுபிடிக்க,
அதிகபட்சம் (₂ 8 பதிவு),
இந்த நடவடிக்கைகள் அல்லது 3,
நடுத்தர உறுப்பு சோதனை, பின் பாதி வரிசை குறைத்து, தேவைப்படும்
அளவு 16 அணிவரிசை, (₂ 16 உள்நுழைய) எடுக்கும் அதேசமயம்
அல்லது 4 நடவடிக்கைகள்.
ஒரே ஒரு இரட்டை அளவு வரிசை 1 மேலும் அறுவை சிகிச்சை.
வரிசை அளவு இருமடங்காக
இந்த குறியீடு மட்டுமே 1 துண்டின் மூலம் இயக்க அதிகரிக்கிறது.
மீண்டும், பிறகு பிளக்கும், பட்டியல் நடுத்தர உறுப்பு சோதனை.
எனவே, இது, மடக்கை நேரம் செயல்பட வேண்டும்
O (log n).
ஆனால், நீங்கள் சொல்ல, காத்திருக்க
பட்டியலில் நீங்கள் தேடும் உறுப்பு எங்கே இந்த நம்பி இல்லை?
என்ன நீங்கள் பார்க்க முதல் உறுப்பு சரியான ஒன்றாக நடக்கும்?
பின்னர், அது மட்டும், 1 நடவடிக்கை எடுக்கும்
பட்டியலில் எப்படி பெரிய விஷயம் இல்லை.
>> கணினி விஞ்ஞானிகள் இன்னும் சொற்கள் ஏன் நன்றாக, என்று
சிறந்த வழக்கு பிரதிபலிக்கும் எந்த அறிகுறியும் சிக்கலை
மற்றும் மிக மோசமான ஒரு வழிமுறையின் நிகழ்ச்சிகள்.
மேலும் ஒழுங்காக, மேல் மற்றும் கீழ் வரம்புகள்
இயக்க வேண்டும்.
இரும தேடல் சிறந்த வழக்கில், நமது உறுப்பு ஆகும்
அங்கே மத்தியில்,
மற்றும் நீ, சீரான இடைவெளியில் அது கிடைக்கும்
வரிசை மீதமுள்ள எப்படி பெரிய விஷயம் இல்லை.
இந்த பயன்படுத்தப்படும் சின்னமாக Ω உள்ளது.
எனவே, இந்த வழிமுறை Ω (1) இயக்க கூறப்படுகிறது.
சிறந்த வழக்கில், அது, விரைவில் உறுப்பு காண்கிறது
வரிசை எப்படி பெரிய விஷயம் இல்லை,
ஆனால் மிக மோசமான நிலையில்,
அது (log n) பிரித்து காசோலைகளை செய்ய வேண்டும்
வரிசைக்கு சரியான உறுப்பு கண்டுபிடிக்க.
மோசமான மேல் வரம்புகளை நீங்கள் ஏற்கனவே தெரியும் என்று பெரிய "ஓ" என்று அழைக்கப்படுகிறது.
எனவே, அது O (log n), ஆனால் Ω (1) தான்.
>> ஒரு நேர்கோட்டு தேடல், இதற்கு மாறாக,
நீங்கள் வரிசை ஒவ்வொரு உறுப்பு வழியாக நடந்து இதில்
நீங்கள் ஒரு கண்டுபிடிக்க,
சிறந்த Ω (1) உள்ளது.
மீண்டும், முதல் உறுப்பு வேண்டும்.
எனவே, அது அணியின் எவ்வளவு பெரிய விஷயமில்லை.
மோசமான நிலையில், அது அணியின் கடைசி உறுப்பு தான்.
அதனால், நீங்கள், அதை கண்டுபிடிக்க வரிசையில் அனைத்து n உறுப்புகள் மூலம் நடக்க வேண்டும்
நீங்கள் ஒரு 3 தேடும் இருந்தால் பிடிக்கும்.
எனவே, அது O (n) நேரத்தில் இயங்கும்
இது அணியின் உறுப்புகள் எண்ணிக்கை விகிதாசார காரணம்.
>> பயன்படுத்தப்படும் ஒரு சின்னமாக Θ உள்ளது.
இந்த இடத்தில் சிறந்த மற்றும் மோசமான நேரங்களில் வழிமுறைகளை விவரிக்க பயன்படுத்தப்படுகிறது
அதே தான்.
இந்த நாங்கள் முந்தைய பற்றி பேசினார் சரம், நீளம் வழிமுறைகளிலும் வழக்கு.
நாம் முன்பு ஒரு மாறி அதை சேமிக்க வேண்டும் என்று, தான்
நாம் சரம் சேமித்து பின்னர் சீரான இடைவெளியில் அதை அணுக.
என்ன எண் இல்லை
நாம் அது மாறி சேமித்து வருகிறோம், நாம் கவனிக்க வேண்டும்.
சிறந்த விஷயம், நாம் அதை பார்க்க
மற்றும் சரம் நீளம் கண்டறிய.
Ω (1) அல்லது சிறந்த வழக்கு தொடர்ந்த நேரத்தில் இவ்வளவு.
மோசமான, இல்லை
நாம் அது பார்த்து சரம் நீளம் கண்டறிய.
எனவே, ஓ (1) அல்லது மோசமான வழக்கில் நிலையான நேரம்.
எனவே, சிறந்த வழக்கு மற்றும் மோசமான நேரங்களில் இருந்து, ஒரே
இந்த Θ (1) நேரத்தில் இயங்க முடியாது.
>> சுருக்கமாக, நாம் குறியீடுகள் திறன் பற்றி காரணம் நல்ல வழிகள் உள்ளன
அவர்கள் ரன் எடுத்து நிஜ உலக நேரம் பற்றி எதுவுமே தெரியாமல்,
இது, வெளியே காரணிகள் நிறைய பாதிக்கப்படுகிறது
வேறுபட்ட வன்பொருள், மென்பொருள், உட்பட
அல்லது உங்கள் குறியீடு பிரத்தியேக.
மேலும், அது எங்களுக்கு என்ன நடக்கும் பற்றி நன்கு காரணங்கள் அனுமதிக்கிறது
போது உள்ளீடுகள் அதிகரிக்கும் அளவு.
>> நீங்கள் ஓ (n) ² வழிமுறை, ஓடி என்றால்
அல்லது மோசமான, ஒரு ஓ (2 ⁿ) வழிமுறை,
வேகமாக வளர்ந்து வரும் வகையான ஒரு,
நீங்கள் உண்மையில் குறைவு கவனிக்க தொடங்க வேண்டும்
நீங்கள் தரவு பெரிய அளவு வேலை தொடங்கும் போது.
>> அந்த அணுகுமுறை சிக்கல் தான். நன்றி.