Semasa saya mengkaji prestasi algoritma, saya terjumpa perkara ini . Ia bukan sahaja memberi gambaran tentang cara temu bual dijalankan di syarikat teknologi besar, tetapi juga membolehkan anda memahami bagaimana masalah algoritma diselesaikan secekap mungkin.
Artikel ini adalah sejenis iringan kepada video tersebut. Di dalamnya saya memberikan ulasan tentang semua penyelesaian yang ditunjukkan, ditambah dengan versi penyelesaian saya sendiri dalam JavaScript. Nuansa setiap algoritma juga dibincangkan.
Kami mengingatkan: untuk semua pembaca "Habr" - diskaun sebanyak 10 rubel apabila mendaftar dalam mana-mana kursus Skillbox menggunakan kod promosi "Habr".
Skillbox mengesyorkan: Kursus praktikal .
Pernyataan masalah
Kami diberi tatasusunan tertib dan nilai tertentu. Ia kemudian diminta untuk mencipta fungsi yang mengembalikan benar atau salah bergantung pada sama ada jumlah mana-mana dua nombor dalam tatasusunan boleh menyamai nilai yang diberikan.
Dalam erti kata lain, adakah terdapat dua integer dalam tatasusunan, x dan y, yang apabila ditambah bersama sama dengan nilai yang ditentukan?
Contoh A
Jika kita diberi tatasusunan [1, 2, 4, 9] dan nilainya ialah 8, fungsi itu akan kembali palsu kerana tiada dua nombor dalam tatasusunan boleh menambah sehingga 8.
Contoh B
Tetapi jika ia adalah tatasusunan [1, 2, 4, 4] dan nilainya ialah 8, fungsi itu harus kembali benar kerana 4 + 4 = 8.
Penyelesaian 1: Kuasa kasar
Kerumitan masa: O(NΒ²).
Kerumitan ruang: O(1).
Maksud yang paling jelas ialah menggunakan sepasang gelung bersarang.
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;
};Penyelesaian ini tidak cekap kerana ia menyemak setiap kemungkinan jumlah dua elemen dalam tatasusunan dan juga membandingkan setiap pasangan indeks dua kali. (Sebagai contoh, apabila i = 1 dan j = 2 sebenarnya sama seperti membandingkan dengan i = 2 dan j = 1, tetapi dalam penyelesaian ini kita mencuba kedua-dua pilihan).
Oleh kerana penyelesaian kami menggunakan sepasang gelung bersarang, ia adalah kuadratik dengan kerumitan masa O(NΒ²).
Penyelesaian 2: Carian Binari
Kerumitan masa: O(Nlog(N)).
Kerumitan ruang: O(1).
Oleh kerana tatasusunan dipesan, kita boleh mencari penyelesaian menggunakan carian binari. Ini adalah algoritma yang paling cekap untuk tatasusunan tertib. Carian binari itu sendiri mempunyai masa berjalan O(log(N)). Walau bagaimanapun, anda masih perlu menggunakan gelung for untuk menyemak setiap elemen terhadap semua nilai lain.
Berikut ialah penyelesaian yang mungkin kelihatan seperti. Untuk membuat perkara yang jelas, kami menggunakan fungsi yang berasingan untuk mengawal carian binari. Dan juga fungsi removeIndex(), yang mengembalikan versi tatasusunan tolak indeks yang diberikan.
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;
};Algoritma bermula dari indeks [0]. Ia kemudian mencipta versi tatasusunan tidak termasuk indeks pertama dan menggunakan carian binari untuk melihat sama ada mana-mana nilai yang tinggal boleh ditambah pada tatasusunan untuk menghasilkan jumlah yang dikehendaki. Tindakan ini dilakukan sekali untuk setiap elemen dalam tatasusunan.
Gelung for itu sendiri akan mempunyai kerumitan masa linear O(N), tetapi di dalam gelung for kita melakukan carian binari, yang memberikan kerumitan masa keseluruhan O(Nlog(N)). Penyelesaian ini lebih baik daripada yang sebelumnya, tetapi masih ada ruang untuk penambahbaikan.
Penyelesaian 3: Masa linear
Kerumitan masa: O(N).
Kerumitan ruang: O(1).
Sekarang kita akan menyelesaikan masalah, mengingati bahawa tatasusunan disusun. Penyelesaiannya adalah dengan mengambil dua nombor: satu di awal dan satu di akhir. Jika keputusan berbeza daripada yang diperlukan, kemudian tukar titik permulaan dan penamat.
Akhirnya kita akan sama ada menemui nilai yang diingini dan mengembalikan benar, atau titik mula dan tamat akan bertumpu dan mengembalikan palsu.
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;
};
Sekarang semuanya baik-baik saja, penyelesaiannya nampaknya optimum. Tetapi siapa yang boleh menjamin bahawa tatasusunan telah dipesan?
Selepas itu, apa?
Pada pandangan pertama, kita boleh memesan tatasusunan dahulu dan kemudian menggunakan penyelesaian di atas. Tetapi bagaimana ini akan menjejaskan masa pelaksanaan?
Algoritma terbaik ialah quicksort dengan kerumitan masa O (Nlog (N)). Jika kita menggunakannya dalam penyelesaian optimum kita, ia akan mengubah prestasinya daripada O(N) kepada O(Nlog(N)). Adakah mungkin untuk mencari penyelesaian linear dengan tatasusunan tidak tertib?
Penyelesaian 4
Kerumitan masa: O(N).
Kerumitan ruang: O(N).
Ya, terdapat penyelesaian linear; untuk melakukan ini, kita perlu mencipta tatasusunan baharu yang mengandungi senarai padanan yang kita cari. Pertukaran di sini adalah lebih banyak penggunaan memori: ia adalah satu-satunya penyelesaian dalam kertas dengan kerumitan ruang yang lebih besar daripada O(1).
Jika nilai pertama tatasusunan yang diberikan ialah 1 dan nilai carian ialah 8, kita boleh menambah nilai 7 pada tatasusunan "nilai carian".
Kemudian, semasa kami memproses setiap elemen tatasusunan, kami boleh menyemak tatasusunan "nilai carian" dan melihat sama ada salah satu daripadanya adalah sama dengan nilai kami. Jika ya, kembalikan benar.
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;
};Asas penyelesaiannya ialah gelung for, yang, seperti yang kita lihat di atas, mempunyai kerumitan masa linear O(N).
Bahagian lelaran kedua fungsi kami ialah Array.prototype.include(), kaedah JavaScript yang akan mengembalikan benar atau palsu bergantung pada sama ada tatasusunan mengandungi nilai yang diberikan.
Untuk mengetahui kerumitan masa Array.prototype.includes(), kita boleh melihat polyfill yang disediakan oleh MDN (dan ditulis dalam JavaScript) atau menggunakan kaedah dalam kod sumber enjin JavaScript seperti 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;
}
});
}Di sini bahagian lelaran Array.prototype.include() ialah gelung sementara dalam langkah 7 yang (hampir) merentasi keseluruhan panjang tatasusunan yang diberikan. Ini bermakna kerumitan masanya juga linear. Oleh kerana ia sentiasa selangkah di belakang tatasusunan utama kami, kerumitan masa ialah O (N + (N - 1)). Menggunakan Notasi O Besar, kami ringkaskannya kepada O(N) - kerana N yang mempunyai kesan paling besar apabila meningkatkan saiz input.
Mengenai kerumitan spatial, tatasusunan tambahan diperlukan yang panjangnya mencerminkan tatasusunan asal (tolak satu, ya, tetapi itu boleh diabaikan), mengakibatkan kerumitan spatial O(N). Nah, peningkatan penggunaan memori memastikan kecekapan maksimum algoritma.
Saya harap anda mendapati artikel itu berguna sebagai tambahan kepada temu bual video anda. Ia menunjukkan bahawa masalah mudah boleh diselesaikan dalam beberapa cara berbeza dengan jumlah sumber yang berbeza digunakan (masa, ingatan).
Skillbox mengesyorkan:
- Kursus dalam talian yang digunakan .
- Kursus dalam talian .
- Kursus tahun praktikal .
Sumber: www.habr.com