Ketika saya mempelajari kinerja algoritma, saya menemukan ini . Ini tidak hanya memberikan gambaran tentang bagaimana wawancara dilakukan di perusahaan teknologi besar, tetapi juga memungkinkan Anda memahami bagaimana masalah algoritmik diselesaikan seefisien mungkin.
Artikel ini semacam pengiring video. Di dalamnya saya memberikan komentar pada semua solusi yang ditampilkan, ditambah solusi versi saya sendiri dalam JavaScript. Nuansa masing-masing algoritma juga dibahas.
Kami mengingatkan: untuk semua pembaca "Habr" - diskon 10 rubel saat mendaftar di kursus Skillbox apa pun menggunakan kode promosi "Habr".
Skillbox merekomendasikan: Tentu saja praktis .
Pernyataan masalah
Kami diberi array terurut dan nilai tertentu. Kemudian diminta untuk membuat fungsi yang mengembalikan nilai benar atau salah tergantung pada apakah jumlah dua angka dalam array dapat sama dengan nilai yang diberikan.
Dengan kata lain, apakah ada dua bilangan bulat dalam array, x dan y, yang bila dijumlahkan sama dengan nilai yang ditentukan?
Contoh A
Jika kita diberi array [1, 2, 4, 9] dan nilainya 8, fungsi tersebut akan mengembalikan false karena tidak ada dua angka dalam array yang dapat berjumlah 8.
Contoh B
Namun jika berupa array [1, 2, 4, 4] dan nilainya 8, fungsinya harus mengembalikan nilai true karena 4 + 4 = 8.
Solusi 1: Kekerasan
Kompleksitas waktu: O(NΒ²).
Kompleksitas ruang: O(1).
Arti yang paling jelas adalah dengan menggunakan sepasang loop 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;
};Solusi ini tidak efisien karena memeriksa setiap kemungkinan jumlah dua elemen dalam array dan juga membandingkan setiap pasangan indeks dua kali. (Misalnya ketika i = 1 dan j = 2 sebenarnya sama dengan membandingkan dengan i = 2 dan j = 1, namun dalam solusi ini kita mencoba kedua opsi tersebut).
Karena solusi kita menggunakan sepasang perulangan for bersarang, maka solusi tersebut berbentuk kuadrat dengan kompleksitas waktu O(NΒ²).
Solusi 2: Pencarian Biner
Kompleksitas waktu: O(Nlog(N)).
Kompleksitas ruang: O(1).
Karena arraynya diurutkan, kita dapat mencari solusinya menggunakan pencarian biner. Ini adalah algoritma paling efisien untuk array terurut. Pencarian biner sendiri memiliki waktu berjalan O(log(N)). Namun, Anda masih perlu menggunakan perulangan for untuk memeriksa setiap elemen terhadap semua nilai lainnya.
Berikut ini solusinya. Untuk memperjelasnya, kami menggunakan fungsi terpisah untuk mengontrol pencarian biner. Dan juga fungsi hapusIndex(), yang mengembalikan versi array dikurangi 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 dimulai dari indeks [0]. Ini kemudian membuat versi array tidak termasuk indeks pertama dan menggunakan pencarian biner untuk melihat apakah ada nilai yang tersisa dapat ditambahkan ke array untuk menghasilkan jumlah yang diinginkan. Tindakan ini dilakukan satu kali untuk setiap elemen dalam array.
Perulangan for itu sendiri akan memiliki kompleksitas waktu linier sebesar O(N), namun di dalam perulangan for kita melakukan pencarian biner, yang menghasilkan kompleksitas waktu keseluruhan sebesar O(Nlog(N)). Solusi ini lebih baik dari solusi sebelumnya, namun masih ada ruang untuk perbaikan.
Solusi 3: Waktu linier
Kompleksitas waktu: ON(N).
Kompleksitas ruang: O(1).
Sekarang kita akan menyelesaikan masalahnya, mengingat bahwa array sudah diurutkan. Solusinya adalah dengan mengambil dua angka: satu di awal dan satu lagi di akhir. Jika hasilnya berbeda dari yang disyaratkan, ubah titik awal dan akhir.
Pada akhirnya kita akan menemukan nilai yang diinginkan dan mengembalikan nilai benar, atau titik awal dan akhir akan bertemu dan mengembalikan nilai salah.
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, solusinya tampaknya sudah optimal. Tapi siapa yang bisa menjamin bahwa susunannya sudah dipesan?
Lalu bagaimana?
Pada pandangan pertama, kita bisa saja mengurutkan arraynya terlebih dahulu dan kemudian menggunakan solusi di atas. Namun bagaimana pengaruhnya terhadap waktu eksekusi?
Algoritma terbaik adalah quicksort dengan kompleksitas waktu O (Nlog (N)). Jika kita menggunakannya dalam solusi optimal, performanya akan berubah dari O(N) menjadi O(Nlog(N)). Apakah mungkin menemukan solusi linier dengan array tak berurutan?
Solusi 4
Kompleksitas waktu: ON(N).
Kompleksitas ruang: O(N).
Ya, ada solusi linier; untuk melakukan ini, kita perlu membuat array baru yang berisi daftar kecocokan yang kita cari. Pengorbanannya di sini adalah penggunaan memori yang lebih banyak: ini adalah satu-satunya solusi di makalah ini dengan kompleksitas ruang yang lebih besar dari O(1).
Jika nilai pertama dari larik tertentu adalah 1 dan nilai pencariannya adalah 8, kita dapat menambahkan nilai 7 ke larik "nilai pencarian".
Kemudian, saat kita memproses setiap elemen array, kita dapat memeriksa array βnilai pencarianβ dan melihat apakah salah satunya sama dengan nilai kita. Jika ya, kembalikan nilai true.
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;
};Dasar dari solusinya adalah perulangan for, yang, seperti kita lihat di atas, memiliki kompleksitas waktu linier sebesar O(N).
Bagian iteratif kedua dari fungsi kita adalah Array.prototype.include(), sebuah metode JavaScript yang akan mengembalikan nilai benar atau salah bergantung pada apakah array berisi nilai yang diberikan.
Untuk mengetahui kompleksitas waktu Array.prototype.includes(), kita dapat melihat polyfill yang disediakan oleh MDN (dan ditulis dalam JavaScript) atau menggunakan metode dalam kode sumber mesin 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 bagian iteratif dari Array.prototype.include() adalah perulangan while pada langkah 7 yang (hampir) melintasi seluruh panjang array yang diberikan. Artinya kompleksitas waktunya juga linier. Karena selalu satu langkah di belakang array utama kita, kompleksitas waktunya adalah O (N + (N - 1)). Dengan menggunakan Notasi O Besar, kami menyederhanakannya menjadi O(N) - karena Nlah yang memiliki dampak terbesar ketika ukuran input ditingkatkan.
Mengenai kompleksitas spasial, diperlukan array tambahan yang panjangnya mencerminkan array asli (minus satu, ya, tapi itu bisa diabaikan), sehingga menghasilkan kompleksitas spasial O(N). Nah, peningkatan penggunaan memori memastikan efisiensi maksimum dari algoritma.
Saya harap artikel ini bermanfaat bagi Anda sebagai pelengkap wawancara video Anda. Ini menunjukkan bahwa masalah sederhana dapat diselesaikan dengan beberapa cara berbeda dengan jumlah sumber daya yang digunakan (waktu, memori) berbeda.
Skillbox merekomendasikan:
- Kursus online terapan .
- Kursus online .
- Kursus tahun praktis .
Sumber: www.habr.com