Lokacin da nake nazarin aikin algorithms, na ci karo da wannan . Ba wai kawai yana ba da ra'ayi game da yadda ake yin tambayoyi a manyan kamfanonin fasaha ba, amma kuma yana ba ku damar fahimtar yadda ake magance matsalolin algorithmic yadda ya kamata.
Wannan labarin wani nau'i ne na rakiyar bidiyo. A ciki na ba da sharhi kan duk hanyoyin da aka nuna, da sigar nawa na mafita a JavaScript. An kuma tattauna nuances na kowane algorithm.
Muna tunatarwa: ga duk masu karatu na "Habr" - rangwame na 10 rubles lokacin yin rajista a kowane kwas na Skillbox ta amfani da lambar talla "Habr".
Skillbox yana ba da shawarar: Hakikanin hanya .
Tsara matsalar
An ba mu tsari mai tsari da takamaiman ƙima. Sannan ana buƙatar ƙirƙirar aikin da zai dawo gaskiya ko na ƙarya dangane da ko jimlar kowane lambobi biyu a cikin jeri zai iya daidaita ƙimar da aka bayar.
A wasu kalmomi, akwai lambobi biyu a cikin jeri, x da y, waɗanda idan aka haɗa su tare daidai da ƙayyadadden ƙima?
Misali A
Idan an ba mu tsararru [1, 2, 4, 9] kuma ƙimar ta kasance 8, aikin zai dawo karya saboda babu lambobi biyu a cikin tsararrun da za su iya ƙara zuwa 8.
Misali B
Amma idan tsararru ne [1, 2, 4, 4] kuma ƙimar ta kasance 8, aikin yakamata ya dawo gaskiya saboda 4 + 4 = 8.
Magani 1: Ƙarfin ƙarfi
Matsalolin lokaci: O(N²).
Halin sararin samaniya: O(1).
Mafi bayyananniyar ma'anar ita ce amfani da madaukai biyu na gida.
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;
};Wannan maganin ba shi da inganci saboda yana bincika kowane jimlar abubuwa biyu masu yuwuwa a cikin jeri sannan kuma yana kwatanta kowane fihirisa biyu sau biyu. (Misali, lokacin da i = 1 da j = 2 sun kasance daidai da kwatanta da i = 2 da j = 1, amma a cikin wannan bayani muna gwada zaɓuɓɓukan biyu).
Saboda maganinmu yana amfani da madauki biyu na madaukai don madaukai, ma'auni ne tare da rikitarwar lokaci O(N²).
Magani 2: Binciken Binary
Matsalolin lokaci: O(Nlog(N)).
Halin sararin samaniya: O(1).
Tun lokacin da aka ba da umarni, za mu iya nemo mafita ta amfani da binciken binary. Wannan shine mafi inganci algorithm don tsararrun da aka ba da oda. Binciken binary kanta yana da lokacin aiki na O(log(N)). Koyaya, har yanzu kuna buƙatar amfani da madauki don bincika kowane kashi akan duk wasu ƙima.
Ga yadda mafita zata kasance. Don bayyana al'amura, muna amfani da wani aiki daban don sarrafa binciken binary. Haka kuma aikin cire Index(), wanda ke dawo da sigar tsararrun ban da fihirisar da aka bayar.
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;
};Algorithm yana farawa daga fihirisa [0]. Sannan ya ƙirƙiri sigar tsararrun ban da maƙasudin farko kuma yana amfani da bincike na binary don ganin ko za a iya ƙara wasu ƙimar da ta rage a cikin tsararru don samar da adadin da ake so. Ana yin wannan aikin sau ɗaya don kowane kashi a cikin tsararru.
Madauki da kansa zai sami madaidaicin lokaci na O(N), amma a cikin madauki muna yin bincike na binary, wanda ke ba da madaidaicin lokaci na O(Nlog(N)). Wannan maganin ya fi na baya, amma har yanzu akwai sauran damar ingantawa.
Magani 3: Lokacin layi
Matsalolin lokaci: O(N).
Halin sararin samaniya: O(1).
Yanzu za mu magance matsalar, tuna cewa an jera tsararru. Mafita ita ce ɗaukar lambobi biyu: ɗaya a farkon ɗaya kuma a ƙarshe. Idan sakamakon ya bambanta da wanda ake buƙata, to canza wurin farawa da ƙarewa.
A ƙarshe ko dai za mu ci karo da ƙimar da ake so mu dawo da gaskiya, ko kuma abubuwan farawa da ƙarshen za su haɗu su dawo karya.
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;
};
Yanzu komai yana da kyau, mafita yana da alama mafi kyau. Amma wa zai iya ba da tabbacin cewa an yi odar tsararru?
Menene to?
Da kallo na farko, da za mu iya yin odar tsararru da farko sannan mu yi amfani da maganin da ke sama. Amma ta yaya hakan zai shafi lokacin kisa?
Mafi kyawun algorithm shine saurin daidaitawa tare da rikitarwa lokaci O (Nlog (N)). Idan muka yi amfani da shi a cikin mafi kyawun bayani, zai canza aikinsa daga O(N) zuwa O (Nlog(N)). Shin zai yiwu a sami mafita mai layi tare da tsararru mara tsari?
Magani 4
Matsalolin lokaci: O(N).
Halin sararin samaniya: O(N).
Ee, akwai mafita mai layi; don yin wannan, muna buƙatar ƙirƙirar sabon tsararru mai ɗauke da jerin matches waɗanda muke nema. Kasuwancin kashewa anan shine ƙarin amfani da ƙwaƙwalwar ajiya: shine kawai mafita a cikin takarda tare da rikitaccen sararin samaniya fiye da O(1).
Idan ƙimar farko na tsararrun da aka ba ta ita ce 1 kuma ƙimar nema ta kasance 8, za mu iya ƙara ƙimar 7 zuwa tsararrun "ƙimar bincike".
Sa'an nan, yayin da muke sarrafa kowane kashi na tsararrun, za mu iya duba tsararrun "ƙimar bincike" mu ga ko ɗaya daga cikinsu ya yi daidai da ƙimarmu. Idan eh, mayar da gaskiya.
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;
};Tushen maganin shine madauki, wanda, kamar yadda muka gani a sama, yana da madaidaicin lokaci mai rikitarwa na O (N).
Sashe na biyu na aikin mu shine Array.prototype.include(), hanyar JavaScript wacce zata dawo gaskiya ko ta karya dangane da ko tsararrun ta ƙunshi ƙimar da aka bayar.
Don gano wahalar lokaci na Array.prototype.includes(), za mu iya duba polyfill ɗin da MDN ke bayarwa (kuma an rubuta shi cikin JavaScript) ko amfani da wata hanya a cikin lambar tushe na injin JavaScript kamar 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;
}
});
}Anan ɓangaren juzu'i na Array.prototype.include() shine lokacin madauki a mataki na 7 wanda (kusan) ya ratsa duk tsawon tsararrun da aka bayar. Wannan yana nufin cewa ƙayyadaddun lokacinsa shima layi ne. To, tunda ko da yaushe mataki ɗaya ne a bayan babban tsarin mu, wahalar lokaci shine O (N + (N - 1)). Yin amfani da Babban Bayanin O, muna sauƙaƙa shi zuwa O(N) - saboda N shine mafi girman tasiri yayin haɓaka girman shigarwar.
Dangane da hadaddun sararin samaniya, ana buƙatar ƙarin tsararru wanda tsayinsa ya yi daidai da ainihin tsararrun (ban da ɗaya, e, amma ana iya yin watsi da hakan), yana haifar da sarƙaƙƙiyar sararin samaniya. Da kyau, ƙara yawan amfani da ƙwaƙwalwar ajiya yana tabbatar da iyakar ingancin algorithm.
Ina fatan labarin yana da amfani a matsayin kari ga hirar bidiyon ku. Ya nuna cewa ana iya magance matsala mai sauƙi ta hanyoyi daban-daban tare da nau'o'in albarkatun da aka yi amfani da su (lokaci, ƙwaƙwalwar ajiya).
Skillbox yana ba da shawarar:
- Aiwatar da karatun kan layi .
- Darussan kan layi .
- Kwas din shekara mai amfani .
source: www.habr.com