Mentre studiavo le prestazioni degli algoritmi, mi sono imbattuto in questo . Non solo dà un'idea di come vengono condotte le interviste presso le grandi aziende tecnologiche, ma consente anche di capire come i problemi algoritmici vengono risolti nel modo più efficiente possibile.
Questo articolo è una sorta di accompagnamento al video. In esso fornisco commenti su tutte le soluzioni mostrate, oltre alla mia versione della soluzione in JavaScript. Vengono inoltre discusse le sfumature di ciascun algoritmo.
Ti ricordiamo: per tutti i lettori di "Habr" - uno sconto di 10 rubli al momento dell'iscrizione a qualsiasi corso Skillbox utilizzando il codice promozionale "Habr".
Skillbox consiglia: Corso pratico .
Formulazione del problema
Ci viene fornito un array ordinato e un valore specifico. Viene quindi chiesto di creare una funzione che restituisca vero o falso a seconda che la somma di due numeri qualsiasi nell'array possa essere uguale a un determinato valore.
In altre parole, ci sono due numeri interi nell'array, xey, che quando sommati insieme equivalgono al valore specificato?
Esempio A
Se ci viene fornito un array [1, 2, 4, 9] e il valore è 8, la funzione restituirà false perché non è possibile sommare due numeri nell'array fino a 8.
Esempio B
Ma se è un array [1, 2, 4, 4] e il valore è 8, la funzione dovrebbe restituire vero perché 4 + 4 = 8.
Soluzione 1: forza bruta
Complessità temporale: O(N²).
Complessità spaziale: O(1).
Il significato più ovvio è utilizzare una coppia di cicli nidificati.
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 è efficiente perché controlla ogni possibile somma di due elementi nell'array e confronta anche ogni coppia di indici due volte. (Ad esempio, quando i = 1 e j = 2 è in realtà lo stesso 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 nidificati, è quadratica con complessità temporale 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 stessa ha un tempo di esecuzione di O(log(N)). Tuttavia, è comunque necessario utilizzare un ciclo for per verificare ciascun elemento rispetto a tutti gli altri valori.
Ecco come potrebbe essere una soluzione. Per chiarire le cose, utilizziamo una funzione separata per controllare la ricerca binaria. E anche la funzione RemoveIndex(), che restituisce la versione dell'array meno l'indice specificato.
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;
};L'algoritmo parte dall'indice [0]. Quindi crea una versione dell'array escludendo il primo indice e utilizza la ricerca binaria per vedere se uno qualsiasi dei valori rimanenti può essere aggiunto all'array per produrre la somma desiderata. Questa azione viene eseguita una volta per ciascun elemento dell'array.
Il ciclo for stesso avrà una complessità temporale lineare di O(N), ma all'interno del ciclo for eseguiamo una ricerca binaria, che fornisce una complessità temporale complessiva di O(Nlog(N)). Questa soluzione è migliore della precedente, ma c’è ancora margine di miglioramento.
Soluzione 3: tempo lineare
Complessità temporale: O(N).
Complessità spaziale: O(1).
Adesso risolveremo il problema ricordando che l'array è ordinato. La soluzione è prendere due numeri: uno all'inizio e uno alla fine. Se il risultato è diverso da quello richiesto, modificare i punti iniziale e finale.
Alla fine incontreremo il valore desiderato e restituiremo true, oppure i punti iniziale e finale convergeranno e restituiranno false.
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;
};
Adesso va tutto bene, la soluzione sembra essere ottimale. Ma chi può garantire che l'array sia stato ordinato?
Che cosa allora?
A prima vista, avremmo potuto semplicemente ordinare prima l'array e poi utilizzare la soluzione sopra. Ma come influirà questo sui tempi di esecuzione?
L'algoritmo migliore è il Quicksort con complessità temporale O (Nlog (N)). Se lo utilizziamo nella nostra soluzione ottimale, 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).
Complessità spaziale: O(N).
Sì, esiste una soluzione lineare; per fare ciò dobbiamo creare un nuovo array contenente l'elenco delle corrispondenze che stiamo cercando. Il compromesso qui è un maggiore utilizzo della memoria: è l'unica soluzione nel documento con una complessità spaziale maggiore di O(1).
Se il primo valore di un dato array è 1 e il valore di ricerca è 8, possiamo aggiungere il valore 7 all'array "valori di ricerca".
Quindi, mentre elaboriamo ciascun elemento dell'array, possiamo controllare l'array di "valori di ricerca" e vedere se uno di essi è uguale al nostro valore. Se sì, restituisci vero.
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 pari a 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 il valore specificato.
Per capire la complessità temporale di Array.prototype.includes(), possiamo guardare il polyfill fornito da MDN (e scritto in JavaScript) o utilizzare un metodo nel codice sorgente di un 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() è il ciclo while nel passaggio 7 che (quasi) attraversa l'intera lunghezza dell'array specificato. Ciò significa che anche la sua complessità temporale è lineare. Bene, poiché è sempre un passo indietro rispetto al nostro array principale, la complessità temporale è O (N + (N - 1)). Usando la notazione Big O, la semplifichiamo in O(N), perché è N che ha l'impatto maggiore quando si aumenta la dimensione dell'input.
Per quanto riguarda la complessità spaziale, è necessario un array aggiuntivo la cui lunghezza rispecchi l'array originale (meno uno, sì, ma può essere ignorato), risultando in una complessità spaziale O(N). Ebbene, un maggiore utilizzo della memoria garantisce la massima efficienza dell'algoritmo.
Spero che troverai utile l'articolo come supplemento alla tua video intervista. Mostra che un problema semplice può essere risolto in molti modi diversi con diverse quantità di risorse utilizzate (tempo, memoria).
Skillbox consiglia:
- Corso online applicato .
- Corso online .
- Corso pratico annuale .
Fonte: habr.com