அல்காரிதம் சிக்கலானது

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

• ஆடைகள்
• சுத்தமான
• ஊட்டி

இந்த முடிவை அடைய எந்த அல்காரிதம் உங்களை அனுமதிக்கிறது?

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

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

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

இத்தகைய செயல்களின் வரிசை நம் பணியை நிறைவேற்றுமா? ஆம், அது நிச்சயமாக இருக்கும். இந்த தீர்வு திறமையானதா ? அரிதாக. அல்காரிதம்களின் மற்றொரு மிக முக்கியமான அம்சங்களுக்கு இங்கே வருகிறோம்: அவற்றின் செயல்திறன் . இந்த பணியை நிறைவேற்ற பல வழிகள் உள்ளன. ஆனால் நிரலாக்கத்திலும் சாதாரண வாழ்க்கையிலும், நாங்கள் மிகவும் திறமையான வழியைத் தேர்வு செய்ய விரும்புகிறோம். உங்கள் பணியானது வெண்ணெய் தடவிய டோஸ்ட்டைச் செய்வதாக இருந்தால், நீங்கள் கோதுமையை விதைத்து ஒரு பசுவின் பால் கறப்பதன் மூலம் தொடங்கலாம். ஆனால் அது திறமையற்றதாக இருக்கும்தீர்வு - இது நிறைய நேரம் எடுக்கும் மற்றும் நிறைய பணம் செலவாகும். ரொட்டி மற்றும் வெண்ணெய் வாங்குவதன் மூலம் உங்கள் எளிய பணியை நீங்கள் நிறைவேற்றலாம். சிக்கலைத் தீர்க்க இது உங்களை அனுமதித்தாலும், கோதுமை மற்றும் ஒரு மாடு சம்பந்தப்பட்ட வழிமுறை நடைமுறையில் பயன்படுத்த மிகவும் சிக்கலானது. நிரலாக்கத்தில், அல்காரிதம்களின் சிக்கலான தன்மையை மதிப்பிடுவதற்கு பிக் ஓ நோட்டேஷன் எனப்படும் சிறப்புக் குறியீடு உள்ளது. ஒரு அல்காரிதத்தின் செயல்பாட்டின் நேரம் உள்ளீட்டு தரவு அளவைப் பொறுத்தது என்பதை மதிப்பிடுவதை Big O சாத்தியமாக்குகிறது . எளிமையான உதாரணத்தைப் பார்ப்போம்: தரவு பரிமாற்றம். நீங்கள் ஒரு நீண்ட தூரத்திற்கு (உதாரணமாக, 5000 மைல்கள்) கோப்பு வடிவத்தில் சில தகவல்களை அனுப்ப வேண்டும் என்று கற்பனை செய்து பாருங்கள். எந்த அல்காரிதம் மிகவும் பயனுள்ளதாக இருக்கும்? இது நீங்கள் பணிபுரியும் தரவைப் பொறுத்தது. உதாரணமாக, நம்மிடம் 10 எம்பி ஆடியோ கோப்பு உள்ளது என்று வைத்துக்கொள்வோம். இந்த வழக்கில், கோப்புகளை இணையத்தில் அனுப்புவது மிகவும் திறமையான வழிமுறையாகும். இரண்டு நிமிடங்களுக்கு மேல் ஆகாது! எங்கள் வழிமுறையை மீண்டும் கூறுவோம்: "நீங்கள் 5000 மைல்களுக்கு மேல் கோப்புகளின் வடிவத்தில் தகவலை மாற்ற விரும்பினால், நீங்கள் இணையம் வழியாக தரவை அனுப்ப வேண்டும்". சிறப்பானது. இப்போது அதை பகுப்பாய்வு செய்வோம். அது நம் பணியை நிறைவேற்றுமா?சரி, ஆம், அது செய்கிறது. ஆனால் அதன் சிக்கலான தன்மை பற்றி நாம் என்ன சொல்ல முடியும்? ஹ்ம்ம், இப்போது விஷயங்கள் மிகவும் சுவாரஸ்யமாகி வருகின்றன. உண்மை என்னவென்றால், எங்கள் அல்காரிதம் உள்ளீட்டுத் தரவை, அதாவது கோப்புகளின் அளவைப் பொறுத்தது. நம்மிடம் 10 மெகாபைட் இருந்தால், எல்லாம் சரியாகிவிடும். ஆனால் நாம் 500 மெகாபைட் அனுப்ப வேண்டும் என்றால் என்ன செய்வது? 20 ஜிகாபைட்? 500 டெராபைட்? 30 பெட்டாபைட்? எங்கள் அல்காரிதம் வேலை செய்வதை நிறுத்துமா? இல்லை, இந்தத் தரவுகள் அனைத்தும் உண்மையில் மாற்றப்படலாம். அதிக நேரம் எடுக்குமா? ஆம், அது நடக்கும்! எங்கள் அல்காரிதத்தின் ஒரு முக்கிய அம்சத்தை இப்போது நாங்கள் அறிவோம்: அதிக அளவு தரவை அனுப்பினால், அல்காரிதத்தை இயக்க அதிக நேரம் எடுக்கும்.. ஆனால் இந்த உறவைப் பற்றி (உள்ளீடு தரவு அளவு மற்றும் அதை அனுப்புவதற்குத் தேவைப்படும் நேரத்திற்கு இடையே) இன்னும் துல்லியமான புரிதலைப் பெற விரும்புகிறோம். எங்கள் விஷயத்தில், அல்காரிதம் சிக்கலானது நேரியல் . "லீனியர்" என்பது உள்ளீட்டுத் தரவின் அளவு அதிகரிக்கும் போது, ​​அதை அனுப்பும் நேரம் தோராயமாக விகிதாசாரமாக அதிகரிக்கும். டேட்டாவின் அளவு இரட்டிப்பாகும் பட்சத்தில், அதை அனுப்ப வேண்டிய நேரம் இரண்டு மடங்கு அதிகமாக இருக்கும். தரவு 10 மடங்கு அதிகரித்தால், பரிமாற்ற நேரம் 10 மடங்கு அதிகரிக்கும். பெரிய O குறியீட்டைப் பயன்படுத்தி, எங்கள் அல்காரிதத்தின் சிக்கலானது O(n) ஆக வெளிப்படுத்தப்படுகிறது.. எதிர்காலத்திற்கான இந்த குறியீட்டை நீங்கள் நினைவில் கொள்ள வேண்டும் - இது எப்போதும் நேரியல் சிக்கலான வழிமுறைகளுக்குப் பயன்படுத்தப்படுகிறது. இங்கே மாறுபடக்கூடிய பல விஷயங்களைப் பற்றி நாங்கள் பேசவில்லை என்பதை நினைவில் கொள்க: இணைய வேகம், எங்கள் கணினியின் கணக்கீட்டு சக்தி மற்றும் பல. அல்காரிதத்தின் சிக்கலான தன்மையை மதிப்பிடும்போது, ​​இந்தக் காரணிகளைக் கருத்தில் கொள்வதில் அர்த்தமில்லை - எந்த நிகழ்விலும், அவை நம் கட்டுப்பாட்டிற்கு அப்பாற்பட்டவை. பிக் ஓ குறியீடானது அல்காரிதத்தின் சிக்கலை வெளிப்படுத்துகிறது, அது இயங்கும் "சுற்றுச்சூழல்" அல்ல. நமது உதாரணத்துடன் தொடர்வோம். மொத்தமாக 800 டெராபைட் கோப்புகளை அனுப்ப வேண்டும் என்று இறுதியாக அறிந்து கொண்டோம் என்று வைத்துக்கொள்வோம். நிச்சயமாக, இணையத்தில் அவற்றை அனுப்புவதன் மூலம் நம் பணியை நிறைவேற்ற முடியும். ஒரே ஒரு சிக்கல் உள்ளது: நிலையான வீட்டு தரவு பரிமாற்ற விகிதங்களில் (வினாடிக்கு 100 மெகாபிட்), இது தோராயமாக 708 நாட்கள் ஆகும். கிட்டத்தட்ட 2 வருடங்கள்! :O எங்கள் அல்காரிதம் இங்கே சரியாக பொருந்தவில்லை. எங்களுக்கு வேறு தீர்வு தேவை! எதிர்பாராத விதமாக, ஐடி ஜாம்பவான் அமேசான் நம்மை காப்பாற்றுகிறது! அமேசானின் ஸ்னோமொபைல் சேவையானது அதிக அளவிலான டேட்டாவை மொபைல் ஸ்டோரேஜில் அப்லோட் செய்து, டிரக் மூலம் விரும்பிய முகவரிக்கு டெலிவரி செய்ய உதவுகிறது! எனவே, எங்களிடம் ஒரு புதிய அல்காரிதம் உள்ளது! "நீங்கள் 5000 மைல்களுக்கு மேல் கோப்புகளின் வடிவில் தகவலை மாற்ற விரும்பினால், இணையம் வழியாக அனுப்ப 14 நாட்களுக்கு மேல் ஆகும், நீங்கள் அமேசான் டிரக்கில் தரவை அனுப்ப வேண்டும்." இங்கு 14 நாட்களை தன்னிச்சையாக தேர்வு செய்துள்ளோம். நாம் காத்திருக்கக்கூடிய மிக நீண்ட காலம் இது என்று வைத்துக்கொள்வோம். எங்கள் அல்காரிதத்தை பகுப்பாய்வு செய்வோம். அதன் வேகம் பற்றி என்ன? டிரக் 50 மைல் வேகத்தில் சென்றாலும், அது வெறும் 100 மணி நேரத்தில் 5000 மைல்களைக் கடக்கும். இது நான்கு நாட்களுக்கு மேல்! இணையத்தில் தரவை அனுப்பும் விருப்பத்தை விட இது மிகவும் சிறந்தது. இந்த வழிமுறையின் சிக்கலான தன்மை பற்றி என்ன? இதுவும் நேரியல், அதாவது O(n)? இல்லை இது இல்லை. எல்லாவற்றிற்கும் மேலாக, டிரக்கை நீங்கள் எவ்வளவு கனமாக ஏற்றுகிறீர்கள் என்பதைப் பொருட்படுத்தாது - அது இன்னும் அதே வேகத்தில் ஓட்டி சரியான நேரத்தில் வந்து சேரும். எங்களிடம் 800 டெராபைட்கள் இருந்தாலும் அல்லது 10 மடங்கு அதிகமாக இருந்தாலும், டிரக் இன்னும் 5 நாட்களுக்குள் அதன் இலக்கை அடைந்துவிடும். வேறு வார்த்தைகளில் கூறுவதானால், டிரக் அடிப்படையிலான தரவு பரிமாற்ற அல்காரிதம் நிலையான சிக்கலானது. இங்கே, "நிலையானது" என்பது உள்ளீட்டு தரவு அளவைச் சார்ந்தது அல்ல. டிரக்கில் 1 ஜிபி ஃபிளாஷ் டிரைவ் போடுங்கள், அது 5 நாட்களுக்குள் வந்துவிடும். 800 டெராபைட் டேட்டா உள்ள டிஸ்க்குகளில் போட்டால் 5 நாட்களுக்குள் வந்துவிடும். பெரிய O குறியீட்டைப் பயன்படுத்தும் போது, ​​நிலையான சிக்கலானது O(1) ஆல் குறிக்கப்படுகிறது . நாங்கள் O(n) மற்றும் O(1) உடன் பழகியுள்ளோம் , எனவே இப்போது நிரலாக்க உலகில் இன்னும் பல எடுத்துக்காட்டுகளைப் பார்ப்போம் :) உங்களுக்கு 100 எண்களின் வரிசை கொடுக்கப்பட்டுள்ளது என்று வைத்துக்கொள்வோம், மேலும் அவை ஒவ்வொன்றையும் காண்பிப்பதே பணியாகும். பணியகம். forஇந்த பணியைச் செய்யும் ஒரு சாதாரண வளையத்தை நீங்கள் எழுதுகிறீர்கள்

int[] numbers = new int[100];
// ...fill the array with numbers

for (int i: numbers) {
   System.out.println(i);
}

இந்த அல்காரிதத்தின் சிக்கலானது என்ன? நேரியல், அதாவது O(n). நிரல் செய்ய வேண்டிய செயல்களின் எண்ணிக்கை அதற்கு எத்தனை எண்கள் அனுப்பப்படுகின்றன என்பதைப் பொறுத்தது. வரிசையில் 100 எண்கள் இருந்தால், 100 செயல்கள் இருக்கும் (திரையில் சரங்களைக் காண்பிப்பதற்கான அறிக்கைகள்). வரிசையில் 10,000 எண்கள் இருந்தால், 10,000 செயல்களைச் செய்ய வேண்டும். நமது அல்காரிதத்தை எந்த வகையிலும் மேம்படுத்த முடியுமா? இல்லை. எதுவாக இருந்தாலும், கன்சோலில் ஸ்டிரிங்க்களைக் காட்ட, வரிசையின் வழியாக N பாஸ்களை உருவாக்கி, N அறிக்கைகளை இயக்க வேண்டும் . மற்றொரு உதாரணத்தைக் கவனியுங்கள்.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

எங்களிடம் காலியாக உள்ளது LinkedList, அதில் பல எண்களைச் செருகுவோம். எங்கள் எடுத்துக்காட்டில் ஒற்றை எண்ணைச் செருகுவதற்கான வழிமுறை சிக்கலை மதிப்பீடு செய்ய வேண்டும் LinkedList, மேலும் அது பட்டியலில் உள்ள உறுப்புகளின் எண்ணிக்கையைப் பொறுத்தது. பதில் O(1), அதாவது நிலையான சிக்கலானது . ஏன்? பட்டியலின் தொடக்கத்தில் ஒவ்வொரு எண்ணையும் செருகுவோம். கூடுதலாக, நீங்கள் ஒரு எண்ணில் ஒரு எண்ணைச் செருகும்போது LinkedList, ​​உறுப்புகள் எங்கும் நகராது என்பதை நீங்கள் நினைவுபடுத்துவீர்கள். இணைப்புகள் (அல்லது குறிப்புகள்) புதுப்பிக்கப்பட்டன (LinkedList எப்படி வேலை செய்கிறது என்பதை மறந்துவிட்டால், எங்கள் பழைய பாடங்களில் ஒன்றைப் பார்க்கவும் ). எங்கள் பட்டியலில் முதல் எண் x, மற்றும் பட்டியலின் முன்புறத்தில் y எண்ணைச் செருகினால், நாம் செய்ய வேண்டியது இதுதான்:

x.previous  = y;
y.previous = null;
y.next = x;

இணைப்புகளைப் புதுப்பிக்கும் போது, ​​ஏற்கனவே எத்தனை எண்கள் உள்ளனLinkedList , அது ஒன்று அல்லது ஒரு பில்லியனாக இருந்தாலும் நாங்கள் கவலைப்பட மாட்டோம். அல்காரிதத்தின் சிக்கலானது நிலையானது, அதாவது O(1).

மடக்கை சிக்கலானது

பீதியடைய வேண்டாம்! :) "மடக்கை" என்ற வார்த்தை இந்தப் பாடத்தை முடித்துவிட்டு படிப்பதை நிறுத்த வேண்டும் எனத் தூண்டினால், ஓரிரு நிமிடங்கள் அப்படியே இருங்கள். இங்கே பைத்தியக்கார கணிதம் இருக்காது (வேறு இடங்களில் இது போன்ற விளக்கங்கள் நிறைய உள்ளன), மேலும் ஒவ்வொரு உதாரணத்தையும் தனித்தனியாக எடுப்போம். 100 எண்களின் வரிசையில் ஒரு குறிப்பிட்ட எண்ணைக் கண்டுபிடிப்பதே உங்கள் பணி என்று கற்பனை செய்து பாருங்கள். இன்னும் துல்லியமாக, அது இருக்கிறதா இல்லையா என்பதை நீங்கள் சரிபார்க்க வேண்டும். தேவையான எண் கண்டுபிடிக்கப்பட்டவுடன், தேடல் முடிவடைகிறது, மேலும் கன்சோலில் பின்வருவனவற்றைக் காண்பிப்பீர்கள்: "தேவையான எண் கண்டுபிடிக்கப்பட்டது! அதன் குறியீட்டு வரிசையில் = ...." இந்த பணியை நீங்கள் எவ்வாறு நிறைவேற்றுவீர்கள்? இங்கே தீர்வு தெளிவாக உள்ளது: நீங்கள் முதலில் (அல்லது கடைசியாக) தொடங்கி, நீங்கள் தேடும் எண்ணுடன் தற்போதைய எண் பொருந்துகிறதா என்பதைச் சரிபார்க்கவும். அதன்படி, செயல்களின் எண்ணிக்கை நேரடியாக வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கையைப் பொறுத்தது. நம்மிடம் 100 எண்கள் இருந்தால், அடுத்த உறுப்புக்கு 100 முறை சென்று 100 ஒப்பீடுகளைச் செய்ய வேண்டியிருக்கும். 1000 எண்கள் இருந்தால், 1000 ஒப்பீடுகள் இருக்கலாம். இது வெளிப்படையாக நேரியல் சிக்கலானது, அதாவதுO(n) . இப்போது எங்கள் எடுத்துக்காட்டில் ஒரு சுத்திகரிப்பைச் சேர்ப்போம்: நீங்கள் எண்ணைக் கண்டுபிடிக்க வேண்டிய வரிசை ஏறுவரிசையில் வரிசைப்படுத்தப்பட்டுள்ளது . இது எங்கள் பணியைப் பொறுத்தவரை ஏதாவது மாற்றத்தை ஏற்படுத்துமா? விரும்பிய எண்ணை நாங்கள் இன்னும் முரட்டுத்தனமான தேடலைச் செய்யலாம். ஆனால் மாற்றாக, நாம் நன்கு அறியப்பட்ட பைனரி தேடல் அல்காரிதம் பயன்படுத்தலாம் . படத்தில் மேல் வரிசையில், வரிசைப்படுத்தப்பட்ட வரிசையைக் காண்கிறோம். அதில் 23 என்ற எண்ணைக் கண்டுபிடிக்க வேண்டும். எண்களை மீண்டும் மீண்டும் செய்வதற்குப் பதிலாக, வரிசையை 2 பகுதிகளாகப் பிரித்து, வரிசையில் உள்ள நடுத்தர எண்ணைச் சரிபார்க்கிறோம். செல் 4 இல் உள்ள எண்ணைக் கண்டுபிடித்து அதைச் சரிபார்க்கவும் (படத்தில் இரண்டாவது வரிசை). இந்த எண் 16, நாம் தேடுவது 23. தற்போதைய எண் நாம் தேடுவதை விட குறைவாக உள்ளது. அதற்கு என்ன பொருள்? என்று அர்த்தம்அனைத்து முந்தைய எண்களையும் (எண் 16 க்கு முன் உள்ளவை) சரிபார்க்க தேவையில்லை : அவை நாம் தேடுவதை விட குறைவாக இருக்கும் என்று உத்தரவாதம் அளிக்கப்படுகிறது, ஏனெனில் எங்கள் வரிசை வரிசைப்படுத்தப்பட்டுள்ளது! மீதமுள்ள 5 கூறுகளில் தேடலைத் தொடர்கிறோம். குறிப்பு:நாங்கள் ஒரு ஒப்பீட்டை மட்டுமே செய்துள்ளோம், ஆனால் சாத்தியமான விருப்பங்களில் பாதியை நாங்கள் ஏற்கனவே அகற்றிவிட்டோம். எங்களிடம் 5 கூறுகள் மட்டுமே உள்ளன. மீதமுள்ள துணைக்குழுவை மீண்டும் பாதியாகப் பிரித்து, மீண்டும் நடுத்தர உறுப்பை (படத்தில் 3 வது வரிசை) எடுத்து எங்கள் முந்தைய படியை மீண்டும் செய்வோம். எண் 56, அது நாம் தேடும் எண்ணை விட பெரியது. அதற்கு என்ன பொருள்? நாங்கள் மற்றொரு 3 சாத்தியக்கூறுகளை நீக்கிவிட்டோம் என்று அர்த்தம்: எண் 56 மற்றும் அதற்குப் பின் உள்ள இரண்டு எண்கள் (அவை 23 ஐ விட அதிகமாக இருக்கும் என்று உத்தரவாதம் அளிக்கப்பட்டதால், வரிசை வரிசைப்படுத்தப்பட்டுள்ளது). எங்களிடம் சரிபார்க்க இன்னும் 2 எண்கள் மட்டுமே உள்ளன (படத்தின் கடைசி வரிசை) — வரிசை குறியீடுகள் 5 மற்றும் 6 கொண்ட எண்கள். அவற்றில் முதல் எண்ணைச் சரிபார்த்து, நாங்கள் தேடுவதைக் கண்டுபிடிப்போம் - எண் 23! அதன் குறியீடு 5! நமது அல்காரிதத்தின் முடிவுகளைப் பார்ப்போம், பிறகு நாம்' அதன் சிக்கலை பகுப்பாய்வு செய்வேன். மூலம், இது ஏன் பைனரி தேடல் என்று அழைக்கப்படுகிறது என்பதை இப்போது நீங்கள் புரிந்துகொள்கிறீர்கள்: இது தரவை மீண்டும் மீண்டும் பாதியாகப் பிரிப்பதை நம்பியுள்ளது. விளைவு சுவாரசியமாக உள்ளது! எண்ணைத் தேட ஒரு நேரியல் தேடலைப் பயன்படுத்தினால், நமக்கு 10 ஒப்பீடுகள் தேவைப்படும், ஆனால் பைனரி தேடலின் மூலம், பணியை 3 இல் மட்டுமே செய்தோம்! மிக மோசமான நிலையில், 4 ஒப்பீடுகள் இருக்கும் (கடைசி கட்டத்தில் நாம் விரும்பிய எண், மீதமுள்ள சாத்தியக்கூறுகளில் முதலாவதாக இல்லாமல், இரண்டாவதாக இருந்தால், அதன் சிக்கலானது என்ன? இது மிகவும் சுவாரஸ்யமான விஷயம் :) பைனரி தேடல் அல்காரிதம் நேரியல் தேடல் அல்காரிதத்தை விட (அதாவது எளிய மறு செய்கை) அணிவரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கையைச் சார்ந்தது. அணிவரிசையில் 10 கூறுகளுடன் , ஒரு நேரியல் தேடலுக்கு அதிகபட்சம் 10 ஒப்பீடுகள் தேவைப்படும், ஆனால் பைனரி தேடலுக்கு அதிகபட்சம் 4 ஒப்பீடுகள் தேவைப்படும். இது 2.5 மடங்கு வித்தியாசம். ஆனால் 1000 தனிமங்களின் வரிசைக்கு , ஒரு நேரியல் தேடலுக்கு 1000 ஒப்பீடுகள் தேவைப்படும், ஆனால் பைனரி தேடலுக்கு 10 மட்டுமே தேவைப்படும் ! வித்தியாசம் இப்போது 100 மடங்கு! குறிப்பு:அணிவரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை 100 மடங்கு அதிகரித்துள்ளது (10 முதல் 1000 வரை), ஆனால் பைனரி தேடலுக்குத் தேவையான ஒப்பீடுகளின் எண்ணிக்கை 2.5 மடங்கு மட்டுமே (4 முதல் 10 வரை) அதிகரித்துள்ளது. நாம் 10,000 உறுப்புகளைப் பெற்றால் , வேறுபாடு இன்னும் சிறப்பாக இருக்கும்: நேரியல் தேடலுக்கான 10,000 ஒப்பீடுகள் மற்றும் பைனரி தேடலுக்கான மொத்தம் 14 ஒப்பீடுகள் . மீண்டும், தனிமங்களின் எண்ணிக்கை 1000 மடங்கு அதிகரித்தால் (10 முதல் 10000 வரை), ஒப்பீடுகளின் எண்ணிக்கை 3.5 மடங்கு மட்டுமே (4 முதல் 14 வரை) அதிகரிக்கிறது. பைனரி தேடல் அல்காரிதம் சிக்கலானது மடக்கை , அல்லது, நாம் பெரிய O குறியீட்டைப் பயன்படுத்தினால், O(log n). ஏன் அப்படி அழைக்கப்படுகிறது? மடக்கை அதிவேகத்திற்கு எதிர் போன்றது. பைனரி மடக்கை என்பது ஒரு எண்ணைப் பெறுவதற்கு எண் 2 ஐ உயர்த்த வேண்டிய சக்தியாகும். எடுத்துக்காட்டாக, பைனரி தேடல் அல்காரிதம் மூலம் நாம் தேட வேண்டிய 10,000 கூறுகள் உள்ளன. தற்போது, ​​மதிப்புகளின் அட்டவணையைப் பார்த்து, இதைச் செய்ய அதிகபட்சம் 14 ஒப்பீடுகள் தேவைப்படும் என்பதை அறியலாம். ஆனால் அத்தகைய அட்டவணையை யாரும் வழங்கவில்லை என்றால், நீங்கள் சரியான அதிகபட்ச எண்ணிக்கையிலான ஒப்பீடுகளை கணக்கிட வேண்டும் என்றால் என்ன செய்வது? நீங்கள் ஒரு எளிய கேள்விக்கு பதிலளிக்க வேண்டும்: நீங்கள் எந்த சக்தியில் எண் 2 ஐ உயர்த்த வேண்டும், இதன் விளைவாக சரிபார்க்கப்பட வேண்டிய உறுப்புகளின் எண்ணிக்கையை விட அதிகமாகவோ அல்லது சமமாகவோ இருக்கும்? 10,000க்கு, இது 14வது அதிகாரம். 2 முதல் 13வது பவர் மிகவும் சிறியது (8192), ஆனால் 2 முதல் 14வது பவர் = 16384, மற்றும் இந்த எண் எங்கள் நிலையை திருப்திப்படுத்துகிறது (இது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கையை விட அதிகமாகவோ அல்லது சமமாகவோ உள்ளது). மடக்கையை நாங்கள் கண்டறிந்தோம்: 14. நமக்கு எத்தனை ஒப்பீடுகள் தேவைப்படலாம்! :) அல்காரிதம்கள் மற்றும் அல்காரிதமிக் சிக்கலானது ஒரு பாடத்தில் பொருந்தாத ஒரு தலைப்பு. ஆனால் அதை அறிவது மிகவும் முக்கியம்: பல வேலை நேர்காணல்களில் அல்காரிதம்கள் சம்பந்தப்பட்ட கேள்விகள் இருக்கும். கோட்பாட்டிற்காக, உங்களுக்காக சில புத்தகங்களை நான் பரிந்துரைக்க முடியும். நீங்கள் " Grokking Algorithms " உடன் தொடங்கலாம் . இந்த புத்தகத்தில் உள்ள எடுத்துக்காட்டுகள் பைத்தானில் எழுதப்பட்டுள்ளன, ஆனால் புத்தகம் மிகவும் எளிமையான மொழி மற்றும் எடுத்துக்காட்டுகளைப் பயன்படுத்துகிறது. இது ஒரு தொடக்கநிலைக்கு சிறந்த தேர்வாகும், மேலும் என்ன, இது மிகவும் பெரியது அல்ல. மிகவும் தீவிரமான வாசிப்புகளில், ராபர்ட் லாஃபோர் மற்றும் ராபர்ட் செட்ஜ்விக் ஆகியோரின் புத்தகங்கள் எங்களிடம் உள்ளன. இரண்டும் ஜாவாவில் எழுதப்பட்டுள்ளன, இது உங்களுக்குக் கற்றுக்கொள்வதை சற்று எளிதாக்கும். எல்லாவற்றிற்கும் மேலாக, நீங்கள் இந்த மொழியை நன்கு அறிந்திருக்கிறீர்கள்! :) நல்ல கணித திறன் கொண்ட மாணவர்களுக்கு, சிறந்த விருப்பம் தாமஸ் கோர்மனின் புத்தகம் . ஆனால் கோட்பாடு மட்டும் உங்கள் வயிற்றை நிரப்பாது! அறிவு != திறன் . HackerRank மற்றும் LeetCode இல் அல்காரிதம்கள் சம்பந்தப்பட்ட சிக்கல்களைத் தீர்ப்பதை நீங்கள் பயிற்சி செய்யலாம் . கூகுள் மற்றும் ஃபேஸ்புக்கில் நேர்காணல்களின் போது கூட இந்த இணையதளங்களின் பணிகள் பெரும்பாலும் பயன்படுத்தப்படுகின்றன, எனவே நீங்கள் நிச்சயமாக சலிப்படைய மாட்டீர்கள் :) இந்த பாடத்தை வலுப்படுத்த, YouTube இல் பெரிய O குறியீட்டைப் பற்றிய இந்த சிறந்த வீடியோவைப் பார்க்க பரிந்துரைக்கிறேன். அடுத்த பாடங்களில் சந்திப்போம்! :)