Quando studiavo le performance degli algoritmi, mi sono imbattuto in questo . Non solo fornisce un'idea di come si svolgono i colloqui nelle grandi aziende tecnologiche, ma consente anche di capire come affrontare problemi algoritmici in modo molto efficace.
Questo articolo è una sorta di accompagnamento al video. Qui fornisco commenti su tutte le soluzioni mostrate, oltre alla mia versione della soluzione in JavaScript. Vengono anche discussi i dettagli di ciascun algoritmo.
Ricordiamo: per tutti i lettori di «Habr» — sconto di 10.000 rubli per l'iscrizione a qualsiasi corso Skillbox con il codice promozionale «Habr».
Skillbox consiglia: Corso pratico .
Definizione del compito
Ci viene dato un array ordinato e un valore specifico. Poi ci viene chiesto di creare una funzione che restituisca true o false, a seconda che la somma di due numeri qualsiasi dell'array possa essere uguale al valore fornito.
In altre parole, ci sono due numeri interi x e y nell'array che, sommandosi, danno il valore indicato?
Esempio A
Se ci viene dato l'array [1, 2, 4, 9] e il valore 8, la funzione restituirà false, perché nessuna coppia di numeri nell'array può dare 8 come somma.
Esempio B
Ma se si tratta dell'array [1, 2, 4, 4] e del valore 8, la funzione deve restituire true, perché 4 + 4 = 8.
Soluzione 1. Brute Force
Complessità temporale: O(N²).
Complessità spaziale: O(1).
Il significato più ovvio è l'uso di una coppia di cicli annidati.
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;
};Questa soluzione non può essere definita efficiente, poiché controlla ogni possibile somma di due elementi dell'array e confronta ogni coppia di indici due volte. (Ad esempio, quando i = 1 e j = 2 — è effettivamente la stessa cosa che confrontare con i = 2 e j = 1, ma in questa soluzione proviamo entrambe le opzioni).
Poiché la nostra soluzione utilizza una coppia di cicli for annidati, ha una complessità temporale quadratica O(N²).
Soluzione 2. Ricerca binaria
Complessità temporale: O(Nlog(N)).
Complessità spaziale: O(1).
Poiché gli array sono ordinati, possiamo cercare una soluzione utilizzando la ricerca binaria. Questo è l'algoritmo più efficiente per gli array ordinati. La ricerca binaria da sola ha un tempo di esecuzione O(log(N)). Tuttavia, è comunque necessario utilizzare un ciclo for per controllare ogni elemento rispetto a tutti gli altri valori.
Ecco come potrebbe apparire la soluzione. Per rendere tutto chiaro, utilizziamo una funzione separata per il controllo della ricerca binaria. Inoltre, utilizziamo la funzione removeIndex(), che restituisce una versione dell'array senza l'indice specificato.
const findSum = (arr, val) => {
for (let i = 0; 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]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};L'algoritmo inizia dall'indice [0]. Quindi crea una versione dell'array escludendo il primo indice e utilizza la ricerca binaria per verificare se è possibile aggiungere uno dei valori rimanenti all'array per ottenere la somma desiderata. Questa operazione viene eseguita una volta per ciascun elemento dell'array.
Di per sé, il ciclo for avrà una complessità temporale lineare O(N), ma all'interno del ciclo for eseguiamo una ricerca binaria, il che porta a una complessità temporale complessiva di O(N log(N)). Questa soluzione è migliore della precedente, ma ci sono ancora margini di miglioramento.
Soluzione 3. Tempo lineare
Complesso temporale: O(N).
Complessità spaziale: O(1).
Adesso risolveremo il problema ricordando che l'array è ordinato. La soluzione consiste nel prendere due numeri: uno all'inizio e uno alla fine. Se il risultato è diverso da quello richiesto, cambiamo il punto iniziale e finale.
Alla fine, incontreremo il valore desiderato e restituiremo true, oppure i punti iniziali e finali si incontreranno e restituiremo false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Ora va tutto bene, la soluzione sembra ottimale. Ma chi ci garantisce che l'array sia stato ordinato?
E allora?
A prima vista, avremmo potuto semplicemente ordinare l'array e poi utilizzare la soluzione sopra. Ma come influenzerà il tempo di esecuzione?
L'algoritmo migliore è l'ordinamento rapido, con una complessità temporale di O(N log(N)). Se lo utilizziamo nella nostra soluzione ottimale, le sue prestazioni passeranno da O(N) a O(N log(N)). È possibile trovare una soluzione lineare con un array non ordinato?
Soluzione 4
Complesso temporale: O(N).
Complesso spaziale: O(N).
Sì, esiste una soluzione lineare; per questo è necessario creare un nuovo array contenente l'elenco delle corrispondenze che stiamo cercando. Qui il compromesso è un utilizzo più attivo della memoria: questa è l'unica soluzione nell'articolo con una complessità spaziale superiore a O(1).
Se il primo valore di questo array è 1 e il valore cercato è 8, possiamo aggiungere 7 all'array dei 'valori di ricerca'.
Successivamente, elaborando ogni elemento dell'array, possiamo controllare l'array 'valori di ricerca' per vedere se uno di essi è uguale al nostro valore. Se sì, restituiamo 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;
};La base della soluzione è un ciclo for, che, come abbiamo visto sopra, ha una complessità temporale lineare di O(N).
La seconda parte iterativa della nostra funzione è Array.prototype.include(), un metodo JavaScript che restituirà true o false a seconda che l'array contenga un determinato valore.
Per determinare la complessità temporale di Array.prototype.includes(), possiamo considerare il polyfill fornito da MDN (e scritto in JavaScript), oppure esaminare il metodo nel codice sorgente del motore JavaScript, come 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;
}
});
}Qui, la parte iterativa di Array.prototype.include() è un ciclo while al passo 7, che (quasi) attraversa tutta la lunghezza di un dato array. Questo significa che la sua complessità temporale è anch'essa lineare. Poiché si trova sempre un passo indietro rispetto al nostro array principale, la complessità temporale è O(N + (N - 1)). Utilizzando la Notazione Big O, semplifichiamo a O(N), poiché è N ad avere il maggiore impatto all'aumentare della dimensione dell'input.
Per quanto riguarda la complessità spaziale, è necessario un array aggiuntivo la cui lunghezza rispecchia l'array originale (meno uno, sì, ma questo può essere ignorato), il che porta a una complessità spaziale di O(N). Inoltre, l'uso aumentato della memoria garantisce il massimo dell'efficienza dell'algoritmo.
Spero che l'articolo sia utile come appendice al video di colloquio. Mostra come un compito semplice possa essere risolto in modi diversi con varie risorse utilizzate (tempo, memoria).
Skillbox consiglia:
- Corso online applicativo .
- Corso online .
- Corso pratico annuale .
Fonte: habr.com
