Би алгоритмын гүйцэтгэлийг судалж байхдаа ийм зүйл олж мэдсэн . Энэ нь томоохон технологийн корпорациудад ярилцлага хэрхэн явагддаг талаар ойлголт өгөхөөс гадна алгоритмын асуудлыг аль болох үр дүнтэй шийдвэрлэх боломжийг танд олгоно.
Энэ нийтлэл нь видео бичлэгийн нэг төрлийн дагалдах хэрэгсэл юм. Үүн дээр би үзүүлсэн бүх шийдлүүдийн талаар тайлбар өгөхөөс гадна JavaScript дээрх шийдлийн өөрийн хувилбарыг оруулсан болно. Алгоритм бүрийн нарийн ширийн зүйлийг мөн авч үзсэн.
Бид танд сануулж байна: "Хабр" -ын бүх уншигчдад - "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-тэй харьцуулахтай адил боловч энэ шийдэлд бид хоёр сонголтыг туршиж үзэх болно).
Манай шийдэл нь хос nested 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;
};Шийдлийн үндэс нь for давталт бөгөөд дээр дурдсанчлан цаг хугацааны шугаман нарийн төвөгтэй O(N) байна.
Манай функцын хоёрдахь давтагдах хэсэг нь JavaScript арга болох Array.prototype.include() бөгөөд массив нь өгөгдсөн утгыг агуулж байгаа эсэхээс хамаарч үнэн эсвэл худал гэж буцаах болно.
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