Markii aan baranayay waxqabadka algorithms, waxaan la kulmay tan . Ma aha oo kaliya inay bixiso fikrad ah sida wareysiyada loo qabto shirkadaha tiknoolajiyada waaweyn, laakiin sidoo kale waxay kuu ogolaaneysaa inaad fahamto sida dhibaatooyinka algorithmic loo xalliyo sida ugu macquulsan.
Maqaalkani waa nooc ka mid ah la socoshada fiidiyowga. Dhexdeeda waxaan ku bixiyaa faallooyin ku saabsan dhammaan xalalka la muujiyey, oo lagu daray noocayga gaarka ah ee xalka JavaScript. Nuances kasta algorithm ayaa sidoo kale laga hadlay.
Waxaan xusuusineynaa: dhammaan akhristayaasha "Habr" - qiimo dhimis ah 10 rubles marka la qorayo koorso kasta oo Skillbox ah iyadoo la adeegsanayo koodhka xayeysiinta "Habr".
Skillbox waxay ku talinaysaa: Koorso wax ku ool ah .
Abuurista dhibaatada
Waxa nala siiyay hab la amray iyo qiimo gaar ah. Kadib waxaa la waydiistaa in la abuuro hawl soo celisa run ama been iyadoo ku xidhan in wadarta labada tiro ee shaxda ay la mid noqon karaan qiime la bixiyay.
Si kale haddii loo dhigo, ma jiraan laba tirooyin oo ku jira shaxanka, x iyo y, oo marka la isku daro la siman yahay qiimaha la cayimay?
Tusaale A
Haddii nala siiyo array [1, 2, 4, 9] oo qiimihiisu yahay 8, shaqadu waxay ku soo noqonaysaa been sababtoo ah laba lambar oo shaxdu kuma dari karaan ilaa 8.
Tusaale B
Laakiin haddii ay tahay array [1, 2, 4, 4] oo qiimihiisu yahay 8, shaqadu waa inay run ku noqotaa sababtoo ah 4 + 4 = 8.
Xalka 1: Xoog cad
Kakanaanta wakhtiga: O(NΒ²).
Kakanaanta booska: O (1).
Macnaha ugu cad cad waa in la isticmaalo labo siddo oo buul leh.
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;
};Xalkani ma aha mid wax ku ool ah sababtoo ah waxa uu hubinayaa wadar kasta oo suurtogal ah oo ah laba walxood oo ku jira soo diyaarinta iyo sidoo kale isbarbardhigga lammaane kasta oo laba jeer ah. (Tusaale ahaan, marka i = 1 iyo j = 2 dhab ahaantii la mid ah isbarbardhigga i = 2 iyo j = 1, laakiin xalkan waxaan isku daynaa labada doorasho).
Sababtoo ah xalkeenu wuxuu isticmaalaa lammaane buul ah oo loops ah, waa quadratic leh kakanaanta wakhtiga O(NΒ²).
Xalka 2: Raadinta Binary
Kakanaanta wakhtiga: O(Nlog(N)).
Kakanaanta booska: O (1).
Maadaama arraysyada la dalbado, waxaan raadin karnaa xalka anagoo adeegsanayna raadinta binary. Kani waa algoorithm-ka ugu waxtarka badan ee habaynta la dalbaday. Raadinta binary lafteedu waxay leedahay wakhtiga socda ee O(log(N)). Si kastaba ha ahaatee, waxaad weli u baahan tahay inaad isticmaasho loop-ka si aad shay kasta uga hubiso dhammaan qiimayaasha kale.
Waa kan sida uu xalku u ekaan karo. Si aan wax u caddeyno, waxaan isticmaalnaa shaqo gooni ah si aan u xakameyno raadinta binary. Iyo sidoo kale ka saaridaIndex() function, kaas oo soo celinaya nooca array-ga oo laga jaray tusmada la bixiyay.
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 wuxuu ka bilaabmaa index [0]. Kadib waxay abuurtaa nooc ka mid ah array-ga oo ay ku jiraan tusaha koowaad waxayna adeegsataa raadinta binary si ay u aragto haddii mid ka mid ah qiyamka soo haray lagu dari karo array si loo soo saaro wadarta la rabo. Falkan waxa la sameeyaa hal mar shay kasta oo ku jira shaxda.
Loop-ka laftiisa ayaa yeelan doona kakanaanta wakhtiga toosan ee O(N), laakiin gudaha loop-ka waxaanu ku samaynaa raadinta binary, kaas oo siinaya kakanaanta wakhtiga O(Nlog(N)). Xalkani wuu ka fiican yahay kii hore, laakiin weli waxaa jira meel lagu hagaajin karo.
Xalka 3: Waqtiga tooska ah
Kakanaanta wakhtiga: O(N).
Kakanaanta booska: O (1).
Hadda waxaan xallin doonaa dhibaatada, iyadoo la xasuusan yahay in array la soocay. Xalku waa in la qaato laba tiro: mid bilawga iyo mid dhamaadka. Haddii natiijadu ka duwan tahay midda loo baahan yahay, ka dibna beddel dhibcaha bilowga iyo dhammaadka.
Aakhirka ama qiimaha la rabo ayaynu la kulmi doonnaa oo run baynu ku noqonaynaa, ama bilawga iyo dhammaadka ayaa isu iman doona oo been bay ku noqonayaan.
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;
};
Hadda wax walba waa hagaagsan yihiin, xalku wuxuu u muuqdaa mid wanaagsan. Laakiin yaa dammaanad qaadi kara in safafka la dalbaday?
Maxaa haddaba?
Jaleecada hore, waxaan si fudud u dalban karnaa marka hore diyaarinta kadibna isticmaalno xalka sare. Laakiin sidee ayay tani u saamaynaysaa wakhtiga fulinta?
Algorithm-ka ugu fiican waa mid degdeg ah oo leh kakanaanta wakhtiga O (Nlog (N)). Haddii aan u isticmaalno xalkeena ugu fiican, waxay ka beddeli doontaa waxqabadkeeda O (N) ilaa O (Nlog(N)). Suurtagal ma tahay in la helo xal toosan oo aan la amrin?
Xalka 4
Kakanaanta wakhtiga: O(N).
Kakanaanta booska: O(N).
Haa, waxaa jira xal toosan, si aan tan u samayno, waxaan u baahanahay inaan abuurno hannaan cusub oo ka kooban liiska ciyaaraha ee aan raadineyno. Ganacsiga halkan waa isticmaalka xusuusta badan: waa xalka kaliya ee warqada ku jira kakanaanta meel bannaan oo ka weyn O(1).
Haddii qiimaha ugu horreeya ee shaxanka la bixiyay uu yahay 1, qiimaha raadintana uu yahay 8, waxaan ku dari karnaa qiimaha 7 ee "qiyamka raadinta".
Ka dib, marka aan farsameyno qayb kasta oo ka mid ah shaxanka, waxaan hubin karnaa sida ay u kala duwan yihiin "qiimaha raadinta" oo aan aragno haddii mid iyaga ka mid ah uu le'eg yahay qiimahayaga. Hadday haa tahay, ku soo celi run.
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;
};Saldhigga xalku waa loop, kaas oo, sidaan kor ku soo aragnay, leh waqti kakan oo toosan O(N).
Qaybta labaad ee soo noqnoqda ee shaqadeena waa Array.prototype.include(), oo ah habka JavaScript oo soo celin doona run ama been iyadoo ku xidhan haddii shaxdu ka kooban tahay qiimaha la bixiyay.
Si loo ogaado kakanaanta wakhtiga Array.prototype.includes(), waxaanu eegi karnaa buux-buuxinta ay bixiso MDN (oo ku qoran JavaScript) ama isticmaal hab ku jira koodhka isha matoorka JavaScript sida 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;
}
});
}Halkan qaybta soo noqnoqota ee Array.prototype.include() waa inta wareegga 7-aad ee (ku dhawaad) dul marta dhammaan dhererka shaxanka la bixiyay. Tani waxay ka dhigan tahay in kakanaanta wakhtiga ay sidoo kale tahay mid toosan. Hagaag, maadaama ay had iyo jeer hal tallaabo ka danbeyso soo diyaarinteena ugu weyn, kakanaanta wakhtiga waa O (N + (N - 1)). Isticmaalka Big O Notation, waxaanu u fududaynaynaa O(N) -sababtoo ah waa N kan saamaynta ugu wayn ku leh marka la kordhinayo cabbirka wax gelinta.
Marka laga hadlayo kakanaanta boosaska, array dheeraad ah ayaa loo baahan yahay kaas oo dhererkiisu muraayad u yahay shaxdii asalka ahayd (hal laga jaray, haa, laakiin taas waa la iska indho tiri karaa), taasoo keentay kakanaanta goobta O(N). Hagaag, isticmaalka xusuusta oo kordhay ayaa xaqiijinaysa waxtarka ugu sarreeya ee algorithm.
Waxaan rajaynayaa in aad maqaalka faa'iido u hesho si ay u kabto waraysiga fiidyaha. Waxay muujinaysaa in dhibka fudud lagu xallin karo dhowr siyaabood oo kala duwan iyadoo la adeegsanayo xaddi kala duwan oo agab ah (waqti, xusuusta).
Skillbox waxay ku talinaysaa:
- Codsaday koorsada khadka tooska ah .
- Koorso onlayn ah .
- Koorsada sanadka ee wax ku oolka ah .
Source: www.habr.com