Algoritmlarning ishlashini o'rganayotganimda, men bunga duch keldim . Bu nafaqat yirik texnologik korporatsiyalarda intervyular qanday o'tkazilishi haqida tasavvur beradi, balki algoritmik muammolar qanday qilib iloji boricha samarali hal qilinishini tushunishga imkon beradi.
Ushbu maqola videoga o'ziga xos qo'shimcha hisoblanadi. Unda men ko'rsatilgan barcha echimlarga sharhlar beraman, shuningdek, JavaScript-dagi yechimning o'z versiyasi. Har bir algoritmning nuanslari ham muhokama qilinadi.
Sizga eslatib o'tamiz: "Habr" ning barcha o'quvchilari uchun - "Habr" promo-kodidan foydalangan holda har qanday Skillbox kursiga yozilishda 10 000 rubl chegirma.
Skillbox tavsiya qiladi: Amaliy kurs .
Muammoni shakllantirish
Bizga tartiblangan massiv va ma'lum bir qiymat beriladi. Keyin massivdagi har qanday ikkita sonning yig'indisi berilgan qiymatga teng bo'lishi mumkinligiga qarab rost yoki noto'g'ri qaytaruvchi funksiya yaratish so'raladi.
Boshqacha qilib aytganda, massivda ikkita tamsayı, x va y bormi, ular qo'shilganda belgilangan qiymatga teng bo'ladimi?
Misol A
Agar bizga [1, 2, 4, 9] massiv berilsa va qiymati 8 bo'lsa, funktsiya yolg'onni qaytaradi, chunki massivdagi ikkita raqam 8 ga qo'shila olmaydi.
Misol B
Ammo agar u [1, 2, 4, 4] massiv bo'lsa va qiymat 8 bo'lsa, funktsiya true ni qaytarishi kerak, chunki 4 + 4 = 8.
Yechim 1: qo'pol kuch
Vaqt murakkabligi: O(N²).
Kosmik murakkablik: O(1).
Eng aniq ma'no - bir juft ichki o'ralgan halqalardan foydalanish.
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;
};Ushbu yechim samarali emas, chunki u massivdagi ikkita elementning har bir mumkin bo'lgan yig'indisini tekshiradi va har bir indeks juftligini ikki marta taqqoslaydi. (Masalan, qachon i = 1 va j = 2 aslida i = 2 va j = 1 bilan solishtirish bilan bir xil, ammo bu yechimda biz ikkala variantni ham sinab ko'ramiz).
Bizning yechimimiz bir juft nested for loopdan foydalanganligi sababli, u O(N²) vaqt murakkabligi bilan kvadratdir.
Yechim 2: Ikkilik qidiruv
Vaqt murakkabligi: O(Nlog(N)).
Kosmik murakkablik: O(1).
Massivlar tartiblanganligi sababli biz ikkilik qidiruv yordamida yechim izlashimiz mumkin. Bu tartiblangan massivlar uchun eng samarali algoritm. Ikkilik qidiruvning oʻzi O(log(N)) ish vaqtiga ega. Biroq, har bir elementni boshqa barcha qiymatlar bilan tekshirish uchun for tsiklidan foydalanishingiz kerak.
Mana, yechim qanday ko'rinishi mumkin. Hamma narsani aniq qilish uchun biz ikkilik qidiruvni boshqarish uchun alohida funktsiyadan foydalanamiz. Shuningdek, massiv versiyasini minus berilgan indeksni qaytaradigan removeIndex() funksiyasi.
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;
};Algoritm indeks [0] dan boshlanadi. Keyin u birinchi indeksdan tashqari massivning versiyasini yaratadi va kerakli summani ishlab chiqarish uchun qolgan qiymatlardan birortasini massivga qo'shish mumkinligini bilish uchun ikkilik qidiruvdan foydalanadi. Bu harakat massivdagi har bir element uchun bir marta bajariladi.
For tsiklining o'zi O(N) ga teng chiziqli vaqt murakkabligiga ega bo'ladi, lekin for tsikli ichida biz ikkilik qidiruvni amalga oshiramiz, bu esa O(Nlog(N)) ning umumiy vaqt murakkabligini beradi. Bu yechim avvalgisidan yaxshiroq, lekin hali ham yaxshilanish uchun joy bor.
Yechim 3: Chiziqli vaqt
Vaqt murakkabligi: O(N).
Kosmik murakkablik: O(1).
Endi massiv tartiblanganligini eslab, muammoni hal qilamiz. Yechim ikkita raqamni olishdir: biri boshida va biri oxirida. Agar natija talab qilinganidan farq qilsa, boshlang'ich va tugatish nuqtalarini o'zgartiring.
Oxir-oqibat biz kerakli qiymatga duch kelamiz va haqiqatni qaytaramiz yoki boshlang'ich va yakuniy nuqtalar birlashadi va noto'g'ri qaytariladi.
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;
};
Endi hammasi yaxshi, yechim optimal ko'rinadi. Ammo massiv buyurtma qilinganiga kim kafolat bera oladi?
Keyin nima?
Bir qarashda, biz oddiygina massivga buyurtma berishimiz va keyin yuqoridagi yechimdan foydalanishimiz mumkin edi. Ammo bu ijro vaqtiga qanday ta'sir qiladi?
Eng yaxshi algoritm vaqt murakkabligi O (Nlog (N)) bilan tezkor saralashdir. Agar biz uni optimal yechimimizda ishlatsak, u o'z ish faoliyatini O(N) dan O(Nlog(N)) ga o'zgartiradi. Tartibsiz massiv bilan chiziqli yechim topish mumkinmi?
4 hal
Vaqt murakkabligi: O(N).
Kosmik murakkablik: O(N).
Ha, chiziqli yechim bor, buning uchun biz izlayotgan mosliklar ro'yxatini o'z ichiga olgan yangi massiv yaratishimiz kerak. Bu erda o'zaro kelishuv ko'proq xotiradan foydalanishdir: bu O(1) dan kattaroq bo'shliqqa ega bo'lgan qog'ozdagi yagona yechim.
Agar berilgan massivning birinchi qiymati 1 ga, qidiruv qiymati esa 8 ga teng bo‘lsa, “qidiruv qiymatlari” massiviga 7 qiymatini qo‘shishimiz mumkin.
Keyin massivning har bir elementini qayta ishlash jarayonida biz “qidiruv qiymatlari” massivini tekshirishimiz va ulardan biri bizning qiymatimizga teng yoki yo‘qligini ko‘rishimiz mumkin. Ha bo'lsa, rostni qaytaring.
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;
};Yechimning asosini yuqorida ko'rganimizdek, chiziqli vaqt murakkabligi O(N) bo'lgan for tsikli tashkil etadi.
Funktsiyamizning ikkinchi iterativ qismi Array.prototype.include(), massiv berilgan qiymatni o'z ichiga oladimi-yo'qligiga qarab rost yoki noto'g'ri qaytaradigan JavaScript usulidir.
Array.prototype.includes() ning vaqt murakkabligini aniqlash uchun biz MDN tomonidan taqdim etilgan (va JavaScript-da yozilgan) polifillni ko'rib chiqishimiz yoki Google V8 (C++) kabi JavaScript dvigatelining manba kodidagi usuldan foydalanishimiz mumkin.
// 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;
}
});
}Bu erda Array.prototype.include() ning iterativ qismi berilgan massivning butun uzunligini (deyarli) kesib o'tuvchi 7-bosqichdagi while siklidir. Bu shuni anglatadiki, uning vaqt murakkabligi ham chiziqli. Xo'sh, u har doim bizning asosiy massivimizdan bir qadam orqada bo'lganligi sababli, vaqt murakkabligi O (N + (N - 1)). Big O notationdan foydalanib, biz uni O(N) ga soddalashtiramiz - chunki kiritish hajmini oshirishda aynan N eng katta ta'sir ko'rsatadi.
Fazoviy murakkablikka kelsak, uzunligi asl massivni aks ettiradigan qo'shimcha massiv kerak (minus bitta, ha, lekin buni e'tiborsiz qoldirish mumkin), natijada O(N) fazoviy murakkablik paydo bo'ladi. Xotiradan foydalanishning ortishi algoritmning maksimal samaradorligini ta'minlaydi.
Umid qilamanki, maqola sizga video intervyuga qo'shimcha sifatida foydali bo'ladi. Bu shuni ko'rsatadiki, oddiy muammoni har xil miqdordagi resurslar (vaqt, xotira) bilan bir necha xil usullarda hal qilish mumkin.
Skillbox tavsiya qiladi:
- Amaliy onlayn kurs .
- Onlayn kurs .
- Amaliy yillik kurs .
Manba: www.habr.com