Kai studijavau algoritmų veikimą, susidūriau su tuo . Tai ne tik suteikia supratimą apie tai, kaip interviu vyksta didelėse technologijų korporacijose, bet ir leidžia suprasti, kaip algoritminės problemos sprendžiamos kuo efektyviau.
Šis straipsnis yra savotiškas vaizdo įrašo priedas. Jame pateikiu komentarus apie visus parodytus sprendimus, taip pat savo sprendimo versiją JavaScript. Taip pat aptariami kiekvieno algoritmo niuansai.
Primename: visiems „Habr“ skaitytojams – 10 000 rublių nuolaida užsiregistravus į bet kurį „Skillbox“ kursą naudojant „Habr“ reklamos kodą.
„Skillbox“ rekomenduoja: Praktinis kursas .
Problemos teiginys
Mums suteikiamas užsakytas masyvas ir konkreti reikšmė. Tada prašoma sukurti funkciją, kuri grąžina teisingą arba klaidingą, atsižvelgiant į tai, ar bet kurių dviejų skaičių suma masyve gali būti lygi nurodytai reikšmei.
Kitaip tariant, ar masyve yra du sveikieji skaičiai, x ir y, kuriuos sudėjus, lygi nurodyta reikšme?
A pavyzdys
Jei mums bus suteiktas masyvas [1, 2, 4, 9], o reikšmė yra 8, funkcija grąžins klaidingą, nes jokie du masyvo skaičiai negali pridėti iki 8.
B pavyzdys
Bet jei tai masyvas [1, 2, 4, 4], o reikšmė yra 8, funkcija turėtų grąžinti teisingą, nes 4 + 4 = 8.
1 sprendimas: brutali jėga
Laiko sudėtingumas: O(N²).
Erdvės sudėtingumas: O(1).
Akivaizdžiausia reikšmė yra naudoti įdėtų kilpų porą.
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;
};Šis sprendimas nėra efektyvus, nes patikrina kiekvieną įmanomą dviejų masyvo elementų sumą ir lygina kiekvieną indeksų porą du kartus. (Pavyzdžiui, kai i = 1 ir j = 2 iš tikrųjų yra tas pats, kas lyginti su i = 2 ir j = 1, tačiau šiame sprendime bandome abu variantus).
Kadangi mūsų sprendimas naudoja kilpų įdėtą porą, jis yra kvadratinis ir O (N²) laiko sudėtingumas.
2 sprendimas: dvejetainė paieška
Laiko sudėtingumas: O(Nlog(N)).
Erdvės sudėtingumas: O(1).
Kadangi masyvai yra sutvarkyti, sprendimo galime ieškoti naudodami dvejetainę paiešką. Tai efektyviausias užsakytų masyvų algoritmas. Pačios dvejetainės paieškos vykdymo laikas yra O(log(N)). Tačiau vis tiek turite naudoti for kilpą, kad patikrintumėte kiekvieną elementą su visomis kitomis reikšmėmis.
Štai kaip gali atrodyti sprendimas. Kad viskas būtų aišku, dvejetainei paieškai valdyti naudojame atskirą funkciją. Taip pat funkcija removeIndex(), kuri grąžina masyvo versiją atėmus nurodytą indeksą.
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;
};Algoritmas prasideda nuo indekso [0]. Tada sukuriama masyvo versija, neįskaitant pirmojo indekso, ir naudoja dvejetainę paiešką, kad pamatytų, ar kuri nors iš likusių reikšmių gali būti įtraukta į masyvą, kad būtų gauta norima suma. Šis veiksmas atliekamas vieną kartą kiekvienam masyvo elementui.
Pačios for kilpos tiesinis laiko sudėtingumas bus O(N), bet for ciklo viduje atliekame dvejetainę paiešką, kuri suteikia bendrą laiko sudėtingumą O(Nlog(N)). Šis sprendimas yra geresnis nei ankstesnis, tačiau dar yra kur tobulėti.
3 sprendimas: tiesinis laikas
Laiko sudėtingumas: O(N).
Erdvės sudėtingumas: O(1).
Dabar mes išspręsime problemą, prisimindami, kad masyvas yra surūšiuotas. Sprendimas yra paimti du skaičius: vieną pradžioje ir kitą pabaigoje. Jei rezultatas skiriasi nuo reikalaujamo, pakeiskite pradžios ir pabaigos taškus.
Galų gale mes arba susidursime su norima reikšme ir grąžinsime teisingą, arba pradžios ir pabaigos taškai sutaps ir grįš klaidingi.
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;
};
Dabar viskas gerai, sprendimas atrodo optimalus. Bet kas gali garantuoti, kad masyvas buvo užsakytas?
Kas tada?
Iš pirmo žvilgsnio galėjome tiesiog užsisakyti masyvą ir tada naudoti aukščiau pateiktą sprendimą. Bet kaip tai paveiks vykdymo laiką?
Geriausias algoritmas yra greitasis rūšiavimas su laiko sudėtingumu O (Nlog (N)). Jei naudosime jį savo optimaliame sprendime, jis pakeis savo veikimą iš O(N) į O(Nlog(N)). Ar galima rasti tiesinį sprendimą su netvarkingu masyvu?
4 sprendimas
Laiko sudėtingumas: O(N).
Erdvės sudėtingumas: O(N).
Taip, yra linijinis sprendimas; norėdami tai padaryti, turime sukurti naują masyvą, kuriame būtų ieškomų atitikmenų sąrašas. Kompromisas čia yra didesnis atminties naudojimas: tai vienintelis sprendimas popieriuje, kurio erdvės sudėtingumas didesnis nei O(1).
Jei pirmoji nurodyto masyvo reikšmė yra 1, o paieškos reikšmė yra 8, mes galime pridėti reikšmę 7 prie masyvo „paieškos reikšmės“.
Tada, kai apdorojame kiekvieną masyvo elementą, galime patikrinti „paieškos reikšmių“ masyvą ir pamatyti, ar vienas iš jų yra lygus mūsų vertei. Jei taip, grąžinkite tiesa.
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;
};Sprendimo pagrindas yra for kilpa, kurios, kaip matėme aukščiau, tiesinis laiko sudėtingumas yra O (N).
Antroji kartotinė mūsų funkcijos dalis yra Array.prototype.include(), „JavaScript“ metodas, kuris grąžins „true“ arba „false“, atsižvelgiant į tai, ar masyve yra nurodyta reikšmė.
Norėdami išsiaiškinti Array.prototype.includes() laiko sudėtingumą, galime pažvelgti į MDN pateiktą polifillą (ir parašytą „JavaScript“) arba naudoti metodą „JavaScript“ variklio, pvz., „Google V8“ (C++), šaltinio kode.
// 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;
}
});
}Čia kartotinė Array.prototype.include() dalis yra 7 žingsnio while ciklas, kuris (beveik) kerta visą nurodyto masyvo ilgį. Tai reiškia, kad jo laiko sudėtingumas taip pat yra linijinis. Na, kadangi jis visada vienu žingsniu atsilieka nuo mūsų pagrindinio masyvo, laiko sudėtingumas yra O (N + (N - 1)). Naudodami Big O žymėjimą, supaprastiname jį iki O(N), nes būtent N turi didžiausią įtaką didinant įvesties dydį.
Kalbant apie erdvinį sudėtingumą, reikia papildomo masyvo, kurio ilgis atspindi pradinį masyvą (atėmus vieną, taip, bet į tai galima nekreipti dėmesio), todėl erdvinis sudėtingumas yra O(N). Na, o padidėjęs atminties naudojimas užtikrina maksimalų algoritmo efektyvumą.
Tikiuosi, kad straipsnis jums bus naudingas kaip vaizdo interviu papildymas. Tai rodo, kad paprasta problema gali būti išspręsta keliais skirtingais būdais naudojant skirtingą išteklių kiekį (laiką, atmintį).
„Skillbox“ rekomenduoja:
- Taikomas internetinis kursas .
- Internetinis kursas .
- Praktinių metų kursas .
Šaltinis: www.habr.com