Ha ke ntse ke ithuta ts'ebetso ea li-algorithms, ke ile ka kopana le sena . Ha e fane feela ka maikutlo a hore na lipuisano li etsoa joang lik'hamphaning tse kholo tsa theknoloji, empa hape e u lumella ho utloisisa hore na mathata a algorithmic a rarolloa joang ka nepo kamoo ho ka khonehang.
Sengoliloeng sena ke mofuta oa ho tsamaisana le video. Ho eona ke fana ka maikutlo mabapi le litharollo tsohle tse bontšitsoeng, hammoho le mofuta oa ka oa tharollo ho JavaScript. Li-nuances tsa algorithm ka 'ngoe li boetse li tšohloa.
Re hopotsa: bakeng sa babali bohle ba "Habr" - theolelo ea li-ruble tse 10 ha u ngolisa thupelong efe kapa efe ea Skillbox u sebelisa khoutu ea papatso ea "Habr".
Skillbox e khothaletsa: Tsela e sebetsang .
Mokhoa oa bothata
Re fuoa sehlopha se laetsoeng le boleng bo itseng. E ntan'o botsoa ho theha ts'ebetso e khutlisetsang 'nete kapa bohata ho latela hore na kakaretso ea linomoro tse peli tse hlophisitsoeng li ka lekana le boleng bo fanoeng.
Ka mantsoe a mang, na ho na le linomoro tse peli lethathamong, x le y, tseo ha li kopantsoe hammoho li lekanang boleng bo boletsoeng?
Mohlala A
Haeba re fuoa mefuta e mengata [1, 2, 4, 9] 'me boleng ke 8, ts'ebetso e tla khutla e le leshano hobane ha ho linomoro tse peli ka har'a sehlopha tse ka eketsang ho 8.
Mohlala B
Empa haeba e le sehlopha [1, 2, 4, 4] 'me boleng ke 8, mosebetsi o lokela ho khutlela' nete hobane 4 + 4 = 8.
Tharollo ea 1: Matla a sehlōhō
Ho rarahana ha nako: O(N²).
Ho rarahana ha sepakapaka: O(1).
Moelelo o hlakileng ka ho fetesisa ke ho sebelisa li-loops tse behiloeng sehlaheng.
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;
};Tharollo ena ha e sebetse hantle hobane e hlahloba palo e 'ngoe le e 'ngoe e ka khonehang ea likarolo tse peli ka har'a sehlopha hape e bapisa li-indices tse peli habeli. (Ka mohlala, ha ke = 1 le j = 2 e hlile e tšoana le ho bapisa le i = 2 le j = 1, empa tharollong ena re leka likhetho tse peli).
Hobane tharollo ea rona e sebelisa para ea sehlaha bakeng sa loops, e quadratic le O(N²) ho rarahana ha nako.
Tharollo 2: Binary Search
Ho rarahana ha nako: O(Nlog(N)).
Sepakapaka se rarahaneng: O(1).
Kaha lihlopha li hlophisitsoe, re ka batla tharollo ka ho sebelisa lipatlisiso tsa binary. Ena ke algorithm e sebetsang ka ho fetesisa bakeng sa lihlopha tse hlophisitsoeng. Binary search ka boeona e na le nako ea O(log(N)). Leha ho le joalo, o ntse o hloka ho sebelisa for loop ho lekola ntho e ngoe le e ngoe khahlano le litekanyetso tse ling kaofela.
Mona ke hore na tharollo e ka shebahala joang. Ho hlakisa lintho, re sebelisa ts'ebetso e arohaneng ho laola patlo ea binary. Hape le ts'ebetso ea removeIndex(), e khutlisang mofuta oa sehlopha ho tlosa index e fanoeng.
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 e qala ho index [0]. E ntan'o theha mofuta oa sehlopha ntle le index ea pele mme e sebelisa lipatlisiso tsa binary ho bona hore na ho na le boleng bo setseng bo ka eketsoang lethathamong ho hlahisa chelete e batloang. Ketso ena e etsoa hang bakeng sa karolo e 'ngoe le e 'ngoe e hlophisitsoeng.
The for loop ka boeona e tla ba le nako e thata ea nako ea O(N), empa ka hare ho loop re etsa patlisiso ea binary, e fanang ka nako e rarahaneng ea O(Nlog(N)). Tharollo ena e molemo ho feta e fetileng, empa ho ntse ho e-na le sebaka sa ho ntlafatsa.
Tharollo 3: Nako ea mohala
Ho rarahana ha nako: O(N).
Ho rarahana ha sepakapaka: O(1).
Hona joale re tla rarolla bothata, re hopola hore sehlopha se hlophisitsoe. Tharollo ke ho nka linomoro tse peli: e 'ngoe e qalong le e 'ngoe qetellong. Haeba sephetho se fapane le se hlokahalang, joale fetola lintlha tsa ho qala le ho qetela.
Qetellong re tla kopana le boleng bo lakatsehang ebe re khutlela 'nete, kapa lintlha tsa ho qala le tsa ho qetela li tla kopana ebe li khutla e le leshano.
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;
};
Hona joale ntho e 'ngoe le e' ngoe e lokile, tharollo e bonahala e le ntle. Empa ke mang ea ka tiisang hore sehlopha se ne se laetsoe?
Joale ho thoe'ng?
Ha u habanya feela, re ka be re ile ra laela sehlopha pele ebe re sebelisa tharollo e ka holimo. Empa see se tla ama nako ea kahlolo joang?
Algorithm e ntle ka ho fetisisa ke ho hlophisa kapele ka ho rarahana ha nako O (Nlog (N)). Haeba re e sebelisa tharollong ea rona e nepahetseng, e tla fetola ts'ebetso ea eona ho tloha ho O(N) ho ea ho O(Nlog(N)). Na hoa khoneha ho fumana tharollo ea mela e nang le sehlopha se sa laoleheng?
Tharollo 4
Ho rarahana ha nako: O(N).
Ho rarahana ha sepakapaka: O(N).
Ee, ho na le tharollo ea mola; ho etsa sena, re hloka ho theha lethathamo le lecha le nang le lethathamo la lipapali tseo re li batlang. Thekiso mona ke ts'ebeliso ea memori e mengata: ke eona feela tharollo pampiring e nang le bothata ba sebaka se seholo ho feta O(1).
Haeba boleng ba pele ba sehlopha se fanoeng ke 1 'me boleng ba ho batla ke 8, re ka eketsa boleng ba 7 ho "batlisisa boleng".
Joale, ha re ntse re sebetsana le karolo e 'ngoe le e' ngoe ea sehlopha, re ka hlahloba letoto la "batlisisa boleng" mme re bone hore na e 'ngoe ea tsona e lekana le boleng ba rona. Haeba ho joalo, khutlela ho 'nete.
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;
};Motheo oa tharollo ke a for loop, eo, joalo ka ha re bone ka holimo, e nang le nako e thata ea nako ea O(N).
Karolo ea bobeli e pheta-phetoang ea mosebetsi oa rona ke Array.prototype.include(), mokhoa oa JavaScript o tla khutlisa 'nete kapa bohata ho latela hore na sehlopha se na le boleng bo fanoeng.
Ho fumana nako ea ho rarahana ha Array.prototype.includes(), re ka sheba polyfill e fanoeng ke MDN (le e ngotsoeng ka JavaScript) kapa re sebelise mokhoa oa mohloli oa mochine oa JavaScript o kang 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;
}
});
}Mona karolo e pheta-phetoang ea Array.prototype.include() ke loop ea nako mohatong oa 7 eo (hoo e ka bang) e fetang bolelele bohle ba lethathamo le fanoeng. Sena se bolela hore ho rarahana ha nako ea eona le hona hoa mela. Joale, kaha kamehla ke mohato o le mong ka morao ho sehlopha sa rona se seholo, ho rarahana ha nako ke O (N + (N - 1)). Re sebelisa Big O Notation, re e nolofatsa ho O(N) - hobane ke N e nang le tšusumetso e kholo ha e eketsa boholo ba tlhahiso.
Mabapi le ho rarahana ha sebaka, ho hlokahala lethathamo la tlatsetso leo bolelele ba lona bo bonang mofuta oa mantlha (tlosa e le 'ngoe, e, empa seo se ka hlokomolohuoa), se bakang ho rarahana ha sebaka sa O(N). Che, ts'ebeliso e eketsehileng ea memori e netefatsa katleho e kholo ea algorithm.
Ke ts'epa hore o tla fumana sengoloa se le molemo e le tlatsetso puisanong ea hau ea video. E bontša hore bothata bo bonolo bo ka rarolloa ka litsela tse 'maloa tse fapaneng ka lisebelisoa tse fapaneng tse sebelisoang (nako, mohopolo).
Skillbox e khothaletsa:
- Kopo e sebelisitsoeng inthaneteng .
- Tsela ea inthanete .
- Thuto ea selemo e sebetsang .
Source: www.habr.com