Алгоритмдердің өнімділігін зерттеген кезде мен бұған тап болдым . Бұл ірі технологиялық корпорацияларда сұхбат қалай жүргізілетіні туралы түсінік беріп қана қоймайды, сонымен қатар алгоритмдік есептердің мүмкіндігінше тиімді шешілуін түсінуге мүмкіндік береді.
Бұл мақала бейнеге сүйемелдеу түрі болып табылады. Онда мен барлық көрсетілген шешімдерге түсініктеме беремін, сонымен қатар JavaScript-тегі шешімнің жеке нұсқасы. Әр алгоритмнің нюанстары да талқыланады.
Біз еске саламыз: «Хабрдың» барлық оқырмандары үшін - «Habr» жарнамалық кодын пайдаланып кез келген Skillbox курсына жазылу кезінде 10 000 рубль көлемінде жеңілдік.
Skillbox ұсынады: Практикалық курс .
Мәселенің тұжырымы
Бізге реттелген массив және белгілі бір мән беріледі. Содан кейін массивтегі кез келген екі санның қосындысы берілген мәнге тең бола алатындығына байланысты ақиқат немесе жалған мәнін қайтаратын функция жасау сұралады.
Басқаша айтқанда, массивте қосылғанда көрсетілген мәнге тең болатын x және y екі бүтін сан бар ма?
Мысал А
Егер бізге [1, 2, 4, 9] массиві берілсе және мәні 8 болса, функция жалған мәнін қайтарады, себебі массивтегі екі сан 8-ге дейін қосыла алмайды.
B мысалы
Бірақ егер бұл [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 салыстырумен бірдей, бірақ бұл шешімде біз екі нұсқаны да қолданамыз).
Біздің шешіміміз кірістірілген for циклдерін пайдаланатындықтан, ол O(N²) уақыт күрделілігімен квадрат болып табылады.
Шешім 2: Екілік іздеу
Уақыт күрделілігі: O(Nlog(N)).
Кеңістік күрделілігі: O(1).
Массивтер реттелгендіктен, шешімді екілік іздеу арқылы іздей аламыз. Бұл реттелген массивтер үшін ең тиімді алгоритм. Екілік іздеудің өзінде O(log(N)) жұмыс уақыты бар. Дегенмен, әрбір элементті барлық басқа мәндермен салыстыру үшін әлі де for циклін пайдалану қажет.
Міне, шешім қандай болуы мүмкін. Түсінікті болу үшін біз екілік іздеуді басқару үшін бөлек функцияны қолданамыз. Сондай-ақ, берілген индексті алып тастағандағы массив нұсқасын қайтаратын 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 циклінің өзінде O(N) сызықтық уақыт күрделілігі болады, бірақ for циклінің ішінде біз 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) сызықтық уақыт күрделілігіне ие for циклі.
Функциямыздың екінші қайталанатын бөлігі - Array.prototype.include(), массивте берілген мән бар-жоғына байланысты ақиқат немесе жалған мәнді қайтаратын JavaScript әдісі.
Array.prototype.includes() уақытының күрделілігін анықтау үшін MDN (және JavaScript тілінде жазылған) қамтамасыз ететін политолтырғышты қарауға немесе Google V8 (C++) сияқты JavaScript қозғалтқышының бастапқы кодындағы әдісті қолдануға болады.
// 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-қадамдағы while циклі болып табылады. Бұл оның уақыттық күрделілігінің де сызықты екенін білдіреді. Ол әрқашан біздің негізгі массивтен бір қадам артта болғандықтан, уақыт күрделілігі O (N + (N - 1)) болып табылады. Big O белгісін пайдаланып, біз оны O(N) етіп жеңілдетеміз - себебі кіріс өлшемін ұлғайтқанда бұл N ең үлкен әсер етеді.
Кеңістіктік күрделілікке қатысты ұзындығы бастапқы массивті көрсететін қосымша массив қажет (минус бір, иә, бірақ оны елемеуге болады), нәтижесінде O(N) кеңістіктік күрделілік туындайды. Жадты пайдаланудың жоғарылауы алгоритмнің максималды тиімділігін қамтамасыз етеді.
Мақаланы бейне сұхбатыңызға қосымша ретінде пайдалы деп санаймын. Қарапайым есепті әр түрлі ресурстардың (уақыт, жады) пайдалануымен бірнеше түрлі әдістермен шешуге болатынын көрсетеді.
Skillbox ұсынады:
- Қолданбалы онлайн курс .
- Онлайн курс .
- Практикалық курс .
Ақпарат көзі: www.habr.com