Rehefa nandinika ny zava-bitan'ny algorithm aho dia nahita izany . Tsy vitan'ny hoe manome hevitra ny fomba fanaovana dinidinika amin'ny orinasa teknolojia lehibe izany, fa mamela anao koa hahatakatra ny fomba hamahana ny olana algorithmika araka izay azo atao.
Ity lahatsoratra ity dia karazana miaraka amin'ny horonan-tsary. Ao anatin'izany dia manome fanehoan-kevitra momba ny vahaolana rehetra naseho aho, miampy ny dikan-teny manokana amin'ny vahaolana amin'ny JavaScript. Ny nuances amin'ny algorithm tsirairay dia resahina ihany koa.
Mampahatsiahy izahay: ho an'ny mpamaky rehetra ny "Habr" - fihenam-bidy 10 roubles rehefa misoratra anarana amin'ny taranja Skillbox rehetra mampiasa ny code promotional "Habr".
Skillbox dia manoro hevitra: Mazava ho azy .
Fanambarana olana
Omena laharan-kafatra sy sanda manokana isika. Angatahina izy avy eo mba hamorona asa izay mamerina marina na diso, miankina amin'ny hoe mety hitovy sanda nomena ny fitambaran'ny isa roa ao amin'ny array.
Raha lazaina amin'ny teny hafa, misy integer roa ve ao amin'ny array, x sy y, ka rehefa ampiarahina dia mitovy ny sanda voafaritra?
Ohatra A
Raha omena array [1, 2, 4, 9] isika ary 8 ny sandany, dia hiverina diso ilay asa satria tsy misy isa roa ao amin'ny array afaka manampy hatramin'ny 8.
Ohatra B
Fa raha array [1, 2, 4, 4] ary 8 ny sandany dia tokony hiverina marina ilay asa satria 4 + 4 = 8.
Vahaolana 1: Hery mahery
Sarotra ny fotoana: O(N²).
Sarotra ny habaka: O(1).
Ny dikany mazava indrindra dia ny fampiasana tadivavarana misy akany.
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;
};Tsy mahomby io vahaolana io satria manara-maso ny fitambaran'ny singa roa ao amin'ny laha-tahiry izy ary mampitaha indroa isaky ny indices tsirairay. (Ohatra, rehefa i = 1 sy j = 2 dia mitovy amin'ny fampitahana amin'ny i = 2 sy j = 1, fa amin'ity vahaolana ity dia manandrana safidy roa isika).
Satria ny vahaolanay dia mampiasa akany ho an'ny tadivavarana, dia efa-joro miaraka amin'ny fahasarotan'ny fotoana O(N²).
Vahaolana 2: Fikarohana binary
Sarotra ny fotoana: O(Nlog(N)).
Sarotra ny habaka: O(1).
Koa satria ny arrays dia baiko, dia afaka mitady vahaolana amin'ny alalan'ny fikarohana binary. Ity no algorithm mahomby indrindra ho an'ny array voalamina. Ny fikarohana binary dia manana fotoana mandeha O(log(N)). Na izany aza, mbola mila mampiasa for loop ianao hanamarina ny singa tsirairay amin'ny soatoavina hafa rehetra.
Toy izao ny mety ho endriky ny vahaolana. Mba hanazavana ny zava-misy dia mampiasa fiasa mitokana izahay hifehezana ny fikarohana binary. Ary koa ny asa removeIndex (), izay mamerina ny dikan-tenin'ny array minus ny index nomena.
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;
};Ny algorithm dia manomboka amin'ny index [0]. Avy eo dia mamorona dikan-teny ankoatry ny tondro voalohany ary mampiasa fikarohana mimari-droa mba hahitana raha misy sanda sisa tavela azo ampidirina amin'ny array mba hamokarana ny isa irina. Ity hetsika ity dia atao indray mandeha isaky ny singa tsirairay ao amin'ny array.
Ny for loop mihitsy dia hanana fahasarotana amin'ny fotoana andalana O(N), fa ao anatin'ny loop for dia manao fikarohana mimari-droa isika, izay manome fahasarotam-potoana ankapobeny amin'ny O(Nlog(N)). Ity vahaolana ity dia tsara noho ny teo aloha, saingy mbola misy ny fanatsarana.
Vahaolana 3: Time Linear
Sarotra ny fotoana: O(N).
Sarotra ny habaka: O(1).
Ankehitriny dia hamaha ny olana isika, mitadidy fa ny array dia voalamina. Ny vahaolana dia ny maka isa roa: ny iray amin'ny voalohany ary ny iray amin'ny farany. Raha toa ka tsy mitovy amin'ny ilaina ny vokatra, dia ovay ny teboka fanombohana sy fiafarana.
Amin'ny farany dia hahita ny sanda irina isika ary hiverina marina, na ny teboka fanombohana sy fiafarana dia hitambatra ary hiverina diso.
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;
};
Ankehitriny dia tsara ny zava-drehetra, ny vahaolana dia toa tsara indrindra. Iza anefa no afaka miantoka fa nisy baiko ny array?
Ahoana ary?
Raha vao jerena dia afaka nanafatra fotsiny ny array aloha isika ary avy eo nampiasa ny vahaolana etsy ambony. Ahoana anefa no ho fiantraikan'izany amin'ny fotoana famonoana?
Ny algorithm tsara indrindra dia ny quicksort miaraka amin'ny fahasarotan'ny fotoana O (Nlog (N)). Raha mampiasa azy io amin'ny vahaolana tsara indrindra isika, dia hanova ny fahombiazany avy amin'ny O(N) ho O(Nlog(N)). Azo atao ve ny mahita vahaolana tsipika miaraka amin'ny array tsy misy filaharana?
Vahaolana 4
Sarotra ny fotoana: O(N).
Sarotra ny habaka: O(N).
Eny, misy vahaolana tsipika; Mba hanaovana izany, dia mila mamorona array vaovao misy ny lisitry ny lalao izay tadiavintsika. Ny fifampiraharahana eto dia ny fampiasana fitadidiana bebe kokoa: io ihany no vahaolana amin'ny taratasy manana fahasarotana lehibe kokoa noho ny O(1).
Raha 1 ny sanda voalohany amin'ny sanda nomena ary 8 ny sanda fikarohana, dia azontsika ampiana ny sanda 7 amin'ny laharan'ny "soatoavina fikarohana".
Avy eo, rehefa mandinika ny singa tsirairay ao amin'ny laharan-tariby isika, dia afaka manamarina ny laharan'ny "soatoavina fikarohana" ary jereo raha mitovy amin'ny sandantsika ny iray amin'izy ireo. Raha eny, avereno marina.
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;
};Ny fototry ny vahaolana dia for loop, izay, araka ny hitantsika tetsy ambony, dia manana fahasarotana ara-potoana amin'ny O (N).
Ny ampahany faharoa amin'ny asantsika dia Array.prototype.include(), fomba JavaScript izay hiverina marina na diso miankina amin'ny hoe misy ny sanda nomena ny array.
Mba hamantarana ny fahasarotan'ny fotoana Array.prototype.includes(), dia afaka mijery ny polyfill nomen'ny MDN (ary voasoratra amin'ny JavaScript) isika na mampiasa fomba iray ao amin'ny loharano loharanon'ny motera JavaScript toy ny 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;
}
});
}Eto ny ampahany miverimberina amin'ny Array.prototype.include() dia ny tadivavarana eo amin'ny dingana 7 izay (saika) mamakivaky ny halavan'ny laharan-tariby nomena. Midika izany fa linear ihany koa ny fahasarotan'ny fotoana. Eny, satria dingana iray foana ao ambadiky ny laharan-tsaintsika, ny fahasarotan'ny fotoana dia O (N + (N - 1)). Amin'ny fampiasana Big O Notation, dia manatsotra azy ho O(N) - satria N no misy fiantraikany lehibe indrindra rehefa mampitombo ny haben'ny fidirana.
Mikasika ny fahasarotan'ny habakabaka dia ilaina ny laharan-tariby fanampiny izay ny halavany dia mitaratra ny laharan'ny tany am-boalohany (minus iray, eny, saingy azo tsinontsinoavina izany), ka miteraka fahasarotana ara-potoana O(N). Eny, ny fampitomboana ny fampiasana fahatsiarovana dia miantoka ny fahombiazan'ny algorithm.
Manantena aho fa ilainao ilay lahatsoratra ho fanampin'ny tafatafa amin'ny horonan-tsary. Mampiseho izany fa ny olana tsotra dia azo voavaha amin'ny fomba maro samihafa miaraka amin'ny habetsaky ny loharano ampiasaina (fotoana, fitadidiana).
Skillbox dia manoro hevitra:
- Fianarana amin'ny Internet .
- Mazava ho azy amin'ny Internet .
- Taranja fanao isan-taona .
Source: www.habr.com