Quando studiavo le prestazioni degli algoritmi, ho trovato questo . Non solo fornisce un'idea di come si svolgono i colloqui nelle grandi aziende tecnologiche, ma aiuta anche a comprendere come vengono risolti i problemi algoritmici, in modo il più efficace possibile.
Questo articolo è una sorta di accompagnamento al video. Qui fornisco commenti su tutte le soluzioni mostrate e la mia versione della soluzione in JavaScript. Vengono anche discussi i dettagli di ogni 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 fornito un array ordinato e un certo valore. 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 dato.
In altre parole, ci sono due numeri interi x e y nell'array che, sommati, sono uguali al 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 dell'array può sommare a 8.
Esempio B
Ma se l'array è [1, 2, 4, 4] e il valore è 8, la funzione deve restituire true, poiché 4 + 4 = 8.
Soluzione 1. Brute Force
Complessità temporale: O(N²).
Complessità spaziale: O(1).
Il valore più ovvio è utilizzare 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 considerata efficiente, poiché controlla ogni possibile somma di due elementi nell'array e confronta ogni coppia di indici due volte. (Ad esempio, quando i = 1 e j = 2 — è effettivamente la stessa cosa 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, è quadratica con una complessità temporale di 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 array ordinati. La ricerca binaria ha di per sé un tempo di esecuzione O(log(N)). Tuttavia, è comunque necessario utilizzare un ciclo for per controllare ogni elemento con tutti gli altri valori.
Ecco come potrebbe apparire una soluzione. Per rendere tutto chiaro, utilizziamo una funzione separata per gestire la ricerca binaria. Inoltre, abbiamo una funzione removeIndex(), che restituisce una versione dell'array escluso 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 con l'indice [0]. Poi crea una versione dell'array escludendo il primo indice e utilizza la ricerca binaria per verificare se possiamo aggiungere uno dei valori rimanenti all'array per ottenere la somma desiderata. Questa operazione viene eseguita una volta per ogni 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 totale di O(Nlog(N)). Questa soluzione è migliore rispetto alla precedente, ma c'è ancora margine di miglioramento.
Soluzione 3. Tempo lineare
Complessità temporale: O(N).
Complessità spaziale: O(1).
Ora risolveremo il problema, tenendo presente che l'array è ordinato. La soluzione consiste nell prendere due numeri: uno all'inizio e uno alla fine. Se il risultato differisce da quello richiesto, cambiamo il punto iniziale e finale.
Alla fine, o troviamo il valore desiderato e restituiamo true, o i punti iniziale e finale si incontrano e restituiamo 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 garantisce che l'array fosse ordinato?
E allora?
A prima vista, potremmo iniziare semplicemente ordinando l'array e poi utilizzare la soluzione sopra. Ma come influenzerà il tempo di esecuzione?
Il miglior algoritmo è il quicksort con una complessità temporale di O(Nlog(N)). Se lo utilizziamo nella nostra soluzione ottimale, essa cambierà le sue prestazioni da O(N) a O(Nlog(N)). È possibile trovare una soluzione lineare con un array non ordinato?
Soluzione 4
Complessità temporale: O(N).
Complesso spaziale: O(N).
Sì, esiste una soluzione lineare, per questo dobbiamo creare un nuovo array contenente l'elenco delle corrispondenze che stiamo cercando. Il compromesso qui è un uso della memoria più attivo: 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 il valore 7 all'array "valori di ricerca".
Quindi, elaborando ogni elemento dell'array, possiamo controllare l'array "valori di ricerca" e 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 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 o meno il valore specificato.
Per capire la complessità temporale di Array.prototype.includes(), possiamo esaminare il polyfill fornito da MDN (e scritto in JavaScript), oppure fare riferimento al 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 per intero la lunghezza di questo array. Ciò significa che la sua complessità temporale è anch'essa lineare. Poiché è sempre un passo indietro rispetto al nostro array principale, la complessità temporale è O(N + (N - 1)). Utilizzando la notazione Big O, la semplifichiamo a O(N) — perché è N a influenzare maggiormente all'aumentare della dimensione dell'input.
Per quanto riguarda la complessità spaziale, è necessario un array aggiuntivo la cui lunghezza riflette l'array originale (meno uno, sì, ma questo può essere ignorato), il che porta a una complessità spaziale O(N). Ma l'aumento dell'uso della memoria garantisce l'efficienza massima dell'algoritmo.
Spero che l'articolo si riveli utile come integrazione all'intervista video. Dimostra che un problema semplice può essere risolto in diversi modi, utilizzando risorse differenti (tempo, memoria).
Skillbox consiglia:
- Corso online pratico .
- Corso online .
- Corso pratico annuale .
Fonte: habr.com
