நான் அல்காரிதம்களின் செயல்திறனைப் படிக்கும்போது, இதைக் கண்டேன் . பெரிய தொழில்நுட்ப நிறுவனங்களில் நேர்காணல்கள் எவ்வாறு நடத்தப்படுகின்றன என்பது பற்றிய ஒரு யோசனையை வழங்குவதோடு மட்டுமல்லாமல், அல்காரிதம் சிக்கல்கள் எவ்வாறு முடிந்தவரை திறமையாக தீர்க்கப்படுகின்றன என்பதைப் புரிந்துகொள்ளவும் உதவுகிறது.
இந்த கட்டுரை வீடியோவுக்கு ஒரு வகையான துணை. அதில் நான் காட்டப்பட்டுள்ள அனைத்து தீர்வுகள் பற்றிய கருத்துகளையும், ஜாவாஸ்கிரிப்டில் உள்ள தீர்வுக்கான எனது சொந்த பதிப்பையும் வழங்குகிறேன். ஒவ்வொரு அல்காரிதத்தின் நுணுக்கங்களும் விவாதிக்கப்படுகின்றன.
நாங்கள் நினைவூட்டுகிறோம்: "Habr" இன் அனைத்து வாசகர்களுக்கும் - "Habr" விளம்பரக் குறியீட்டைப் பயன்படுத்தி எந்த Skillbox படிப்பிலும் சேரும்போது 10 ரூபிள் தள்ளுபடி.
Skillbox பரிந்துரைக்கிறது: நடைமுறை படிப்பு .
பிரச்சனை அறிக்கை
எங்களுக்கு ஒரு வரிசைப்படுத்தப்பட்ட வரிசை மற்றும் ஒரு குறிப்பிட்ட மதிப்பு வழங்கப்படுகிறது. அணிவரிசையில் உள்ள ஏதேனும் இரண்டு எண்களின் கூட்டுத்தொகை கொடுக்கப்பட்ட மதிப்பிற்குச் சமமாகுமா என்பதைப் பொறுத்து சரி அல்லது தவறு என வழங்கும் செயல்பாட்டை உருவாக்குமாறு கேட்கப்படுகிறது.
வேறு வார்த்தைகளில் கூறுவதானால், வரிசையில் இரண்டு முழு எண்கள் உள்ளன, x மற்றும் y, ஒன்றாக சேர்க்கப்படும் போது குறிப்பிட்ட மதிப்புக்கு சமம்?
உதாரணம் ஏ
நமக்கு ஒரு வரிசை [1, 2, 4, 9] கொடுக்கப்பட்டால், மதிப்பு 8 ஆக இருந்தால், செயல்பாடு தவறானதாக இருக்கும், ஏனெனில் வரிசையில் எந்த இரண்டு எண்களும் 8 வரை சேர்க்க முடியாது.
உதாரணம் பி
ஆனால் அது ஒரு வரிசை [1, 2, 4, 4] மற்றும் மதிப்பு 8 ஆக இருந்தால், செயல்பாடு உண்மையாக இருக்க வேண்டும், ஏனெனில் 4 + 4 = 8.
தீர்வு 1: முரட்டு சக்தி
நேர சிக்கலானது: O(N²).
விண்வெளி சிக்கலானது: O(1).
ஒரு ஜோடி உள்ளமை சுழல்களைப் பயன்படுத்துவதே மிகத் தெளிவான பொருள்.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i !== j && arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};இந்த தீர்வு திறமையானது அல்ல, ஏனெனில் இது வரிசையில் உள்ள இரண்டு உறுப்புகளின் சாத்தியமான ஒவ்வொரு தொகையையும் சரிபார்க்கிறது மற்றும் ஒவ்வொரு ஜோடி குறியீடுகளையும் இரண்டு முறை ஒப்பிடுகிறது. (உதாரணமாக, i = 1 மற்றும் j = 2 ஆகியவை உண்மையில் i = 2 மற்றும் j = 1 உடன் ஒப்பிடும் போது ஒரே மாதிரியாக இருக்கும், ஆனால் இந்த தீர்வில் இரண்டு விருப்பங்களையும் முயற்சிக்கிறோம்).
எங்கள் தீர்வு லூப்களுக்கு ஒரு ஜோடி உள்ளமைவைப் பயன்படுத்துவதால், இது O(N²) நேர சிக்கலுடன் இருபடியாக உள்ளது.
தீர்வு 2: பைனரி தேடல்
நேர சிக்கலானது: O(Nlog(N)).
விண்வெளி சிக்கலானது: O(1).
வரிசைகள் வரிசைப்படுத்தப்பட்டதால், பைனரி தேடலைப் பயன்படுத்தி ஒரு தீர்வைத் தேடலாம். ஆர்டர் செய்யப்பட்ட வரிசைகளுக்கு இது மிகவும் திறமையான அல்காரிதம் ஆகும். பைனரி தேடலில் O(log(N)) இயங்கும் நேரம் உள்ளது. இருப்பினும், ஒவ்வொரு உறுப்பையும் மற்ற எல்லா மதிப்புகளுக்கும் எதிராகச் சரிபார்க்க நீங்கள் இன்னும் for loop ஐப் பயன்படுத்த வேண்டும்.
ஒரு தீர்வு எப்படி இருக்கும் என்பது இங்கே. விஷயங்களை தெளிவுபடுத்த, பைனரி தேடலைக் கட்டுப்படுத்த ஒரு தனி செயல்பாட்டைப் பயன்படுத்துகிறோம். மேலும் removeIndex() செயல்பாடானது, இது வரிசையின் பதிப்பை கொடுக்கப்பட்ட குறியீட்டை கழிக்கும்.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++){
if (binarySearch(removeIndex(arr, i), val - arr[i])) {
return true;
}
};
return false;
};
const removeIndex = (arr, i) => {
return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
const binarySearch = (arr, val) => {
let start = 0;
let end = arr.length - 1;
let pivot = Math.floor(arr.length / 2);
while (start < end) {
if (val < arr[pivot]) {
end = pivot - 1;
} else if (val > arr[pivot]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};அல்காரிதம் குறியீட்டு [0] இலிருந்து தொடங்குகிறது. இது முதல் குறியீட்டைத் தவிர்த்து வரிசையின் பதிப்பை உருவாக்குகிறது மற்றும் விரும்பிய தொகையை உருவாக்க மீதமுள்ள மதிப்புகளில் ஏதேனும் ஒன்றை அணியில் சேர்க்க முடியுமா என்பதைப் பார்க்க பைனரி தேடலைப் பயன்படுத்துகிறது. இந்த செயல் வரிசையில் உள்ள ஒவ்வொரு உறுப்புக்கும் ஒரு முறை செய்யப்படுகிறது.
for loop ஆனது O(N) இன் நேரியல் நேர சிக்கலைக் கொண்டிருக்கும், ஆனால் for loop இன் உள்ளே நாம் ஒரு பைனரி தேடலைச் செய்கிறோம், இது O(Nlog(N)) இன் ஒட்டுமொத்த நேர சிக்கலை அளிக்கிறது. இந்த தீர்வு முந்தையதை விட சிறந்தது, ஆனால் முன்னேற்றத்திற்கான இடம் இன்னும் உள்ளது.
தீர்வு 3: நேரியல் நேரம்
நேர சிக்கலானது: O(N).
விண்வெளி சிக்கலானது: O(1).
இப்போது வரிசை வரிசைப்படுத்தப்பட்டதை நினைவில் வைத்து சிக்கலைத் தீர்ப்போம். தீர்வு இரண்டு எண்களை எடுக்க வேண்டும்: ஒன்று ஆரம்பத்தில் மற்றும் ஒரு இறுதியில். முடிவு தேவையான ஒன்றிலிருந்து வேறுபட்டால், தொடக்க மற்றும் முடிவு புள்ளிகளை மாற்றவும்.
இறுதியில் நாம் விரும்பிய மதிப்பைச் சந்தித்து உண்மைக்குத் திரும்புவோம், அல்லது தொடக்க மற்றும் முடிவுப் புள்ளிகள் ஒன்றிணைந்து தவறானதாகத் திரும்பும்.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start < end) {
let sum = arr[start] + arr[end];
if (sum > val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};
இப்போது எல்லாம் சரியாகிவிட்டது, தீர்வு உகந்ததாகத் தெரிகிறது. ஆனால் வரிசை ஆர்டர் செய்யப்பட்டது என்று யார் உத்தரவாதம் அளிக்க முடியும்?
பிறகு என்ன?
முதல் பார்வையில், நாம் முதலில் வரிசையை ஆர்டர் செய்து, மேலே உள்ள தீர்வைப் பயன்படுத்தியிருக்கலாம். ஆனால் இது செயல்படுத்தும் நேரத்தை எவ்வாறு பாதிக்கும்?
O (Nlog (N)) சிக்கலான நேரத்துடன் கூடிய விரைவான வரிசைப்படுத்தல் சிறந்த வழிமுறையாகும். நமது உகந்த தீர்வில் இதைப் பயன்படுத்தினால், அது அதன் செயல்திறனை O(N) இலிருந்து O(Nlog(N)) ஆக மாற்றிவிடும். வரிசைப்படுத்தப்படாத வரிசையுடன் நேரியல் தீர்வைக் கண்டுபிடிக்க முடியுமா?
4 தீர்வு
நேர சிக்கலானது: O(N).
விண்வெளி சிக்கலானது: O(N).
ஆம், ஒரு நேரியல் தீர்வு உள்ளது; இதைச் செய்ய, நாம் தேடும் போட்டிகளின் பட்டியலைக் கொண்ட புதிய வரிசையை உருவாக்க வேண்டும். இங்கே வர்த்தகம் என்பது அதிக நினைவகப் பயன்பாடாகும்: O(1) ஐ விட அதிகமான இடச் சிக்கலுடன் காகிதத்தில் உள்ள ஒரே தீர்வு இதுவாகும்.
கொடுக்கப்பட்ட வரிசையின் முதல் மதிப்பு 1 மற்றும் தேடல் மதிப்பு 8 எனில், "தேடல் மதிப்புகள்" வரிசையில் மதிப்பு 7 ஐ சேர்க்கலாம்.
பின்னர், வரிசையின் ஒவ்வொரு உறுப்பையும் செயலாக்கும்போது, "தேடல் மதிப்புகளின்" வரிசையைச் சரிபார்த்து, அவற்றில் ஒன்று நமது மதிப்புக்கு சமமாக இருக்கிறதா என்று பார்க்கலாம். ஆம் எனில், உண்மை என்று திரும்பவும்.
const findSum = (arr, val) => {
let searchValues = [val - arr[0]];
for (let i = 1; i < arr.length; i++) {
let searchVal = val - arr[i];
if (searchValues.includes(arr[i])) {
return true;
} else {
searchValues.push(searchVal);
}
};
return false;
};தீர்வுக்கான அடிப்படையானது லூப் ஆகும், இது நாம் மேலே பார்த்தது போல், O(N) இன் நேரியல் நேர சிக்கலைக் கொண்டுள்ளது.
எங்கள் செயல்பாட்டின் இரண்டாவது செயல்பாட்டின் பகுதி Array.prototype.include(), இது ஒரு ஜாவாஸ்கிரிப்ட் முறையாகும், இது வரிசை கொடுக்கப்பட்ட மதிப்பைக் கொண்டிருக்கிறதா என்பதைப் பொறுத்து சரி அல்லது தவறானது.
Array.prototype.includes() இன் நேர சிக்கலைக் கண்டறிய, MDN வழங்கிய பாலிஃபில் (மற்றும் ஜாவாஸ்கிரிப்ட்டில் எழுதப்பட்டுள்ளது) அல்லது Google V8 (C++) போன்ற ஜாவாஸ்கிரிப்ட் இயந்திரத்தின் மூலக் குறியீட்டில் உள்ள முறையைப் பயன்படுத்தலாம்.
// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
Object.defineProperty(Array.prototype, 'includes', {
value: function(valueToFind, fromIndex) {
if (this == null) {
throw new TypeError('"this" is null or not defined');
}
// 1. Let O be ? ToObject(this value).
var o = Object(this);
// 2. Let len be ? ToLength(? Get(O, "length")).
var len = o.length >>> 0;
// 3. If len is 0, return false.
if (len === 0) {
return false;
}
// 4. Let n be ? ToInteger(fromIndex).
// (If fromIndex is undefined, this step produces the value 0.)
var n = fromIndex | 0;
// 5. If n ≥ 0, then
// a. Let k be n.
// 6. Else n < 0,
// a. Let k be len + n.
// b. If k < 0, let k be 0.
var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
function sameValueZero(x, y) {
return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
}
// 7. Repeat, while k < len
while (k < len) {
// a. Let elementK be the result of ? Get(O, ! ToString(k)).
// b. If SameValueZero(valueToFind, elementK) is true, return true.
if (sameValueZero(o[k], valueToFind)) {
return true;
}
// c. Increase k by 1.
k++;
}
// 8. Return false
return false;
}
});
}இங்கே Array.prototype.include() இன் மறுசெயல் பகுதியானது, கொடுக்கப்பட்ட வரிசையின் முழு நீளத்தையும் (கிட்டத்தட்ட) கடந்து செல்லும் படி 7 இல் உள்ள லூப் ஆகும். இதன் பொருள் அதன் நேர சிக்கலும் நேரியல் ஆகும். சரி, இது எப்பொழுதும் எங்கள் முக்கிய வரிசையில் ஒரு படி பின்னால் இருப்பதால், நேர சிக்கலானது O (N + (N - 1)) ஆகும். பிக் ஓ குறியீட்டைப் பயன்படுத்தி, அதை O(N) ஆக எளிதாக்குகிறோம் - ஏனெனில் உள்ளீடு அளவை அதிகரிக்கும் போது N தான் அதிக தாக்கத்தை ஏற்படுத்துகிறது.
இடஞ்சார்ந்த சிக்கலான தன்மையைப் பொறுத்தவரை, ஒரு கூடுதல் அணிவரிசை தேவைப்படுகிறது, அதன் நீளம் அசல் வரிசையை பிரதிபலிக்கிறது (கழித்தல் ஒன்று, ஆம், ஆனால் அது புறக்கணிக்கப்படலாம்), இதன் விளைவாக O(N) இடஞ்சார்ந்த சிக்கலானது. சரி, அதிகரித்த நினைவக பயன்பாடு அல்காரிதத்தின் அதிகபட்ச செயல்திறனை உறுதி செய்கிறது.
உங்கள் வீடியோ நேர்காணலுக்கு துணையாக கட்டுரை பயனுள்ளதாக இருக்கும் என்று நம்புகிறேன். வெவ்வேறு அளவு வளங்கள் (நேரம், நினைவகம்) மூலம் ஒரு எளிய சிக்கலை பல்வேறு வழிகளில் தீர்க்க முடியும் என்பதை இது காட்டுகிறது.
Skillbox பரிந்துரைக்கிறது:
- ஆன்லைன் படிப்புக்கு விண்ணப்பித்தேன் .
- ஆன்லைன் படிப்பு .
- நடைமுறை ஆண்டு படிப்பு .
ஆதாரம்: www.habr.com