Cando estudaba o rendemento dos algoritmos, atopeime con isto . Non só dá unha idea de como se realizan as entrevistas nas grandes corporacións tecnolóxicas, senón que tamén permite comprender como se resolven os problemas algorítmicos da forma máis eficiente posible.
Este artigo é unha especie de acompañamento do vídeo. Nela facilito comentarios sobre todas as solucións mostradas, ademais da miña propia versión da solución en JavaScript. Tamén se comentan os matices de cada algoritmo.
Recordámolo: para todos os lectores de "Habr" - un desconto de 10 rublos ao inscribirse en calquera curso de Skillbox usando o código promocional "Habr".
Skillbox recomenda: Curso práctico .
Declaración de problemas
Dámosnos unha matriz ordenada e un valor específico. A continuación, pídese que cree unha función que devolva verdadeiro ou falso dependendo de se a suma de dous números calquera da matriz pode ser igual a un valor dado.
Noutras palabras, hai dous números enteiros na matriz, x e y, que cando se suman son iguais ao valor especificado?
Exemplo A
Se nos dá unha matriz [1, 2, 4, 9] e o valor é 8, a función devolverá false porque non hai dous números da matriz que suman 8.
Exemplo B
Pero se é unha matriz [1, 2, 4, 4] e o valor é 8, a función debería devolver verdadeiro porque 4 + 4 = 8.
Solución 1: forza bruta
Complexidade temporal: O(N²).
Complexidade espacial: O(1).
O significado máis obvio é usar un par de bucles aniñados.
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;
};Esta solución non é eficiente porque verifica todas as posibles sumas de dous elementos na matriz e tamén compara cada par de índices dúas veces. (Por exemplo, cando i = 1 e j = 2 é realmente o mesmo que comparar con i = 2 e j = 1, pero nesta solución probamos as dúas opcións).
Como a nosa solución usa un par de bucles for anidados, é cuadrática con complexidade temporal O(N²).
Solución 2: Busca binaria
Complexidade temporal: O(Nlog(N)).
Complexidade espacial: O(1).
Dado que as matrices están ordenadas, podemos buscar unha solución mediante a busca binaria. Este é o algoritmo máis eficiente para matrices ordenadas. A propia busca binaria ten un tempo de execución de O(log(N)). Non obstante, aínda debes usar un bucle for para comprobar cada elemento con todos os demais valores.
Aquí tes como pode ser unha solución. Para aclarar as cousas, usamos unha función separada para controlar a busca binaria. E tamén a función removeIndex(), que devolve a versión da matriz menos o índice indicado.
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;
};O algoritmo parte do índice [0]. A continuación, crea unha versión da matriz excluíndo o primeiro índice e usa a busca binaria para ver se se pode engadir algún dos valores restantes á matriz para producir a suma desexada. Esta acción realízase unha vez por cada elemento da matriz.
O propio bucle for terá unha complexidade temporal lineal de O(N), pero dentro do bucle for realizamos unha busca binaria, o que dá unha complexidade temporal global de O(Nlog(N)). Esta solución é mellor que a anterior, pero aínda hai marxe de mellora.
Solución 3: Tempo lineal
Complexidade temporal: O(N).
Complexidade espacial: O(1).
Agora imos resolver o problema, lembrando que a matriz está ordenada. A solución é tomar dous números: un ao principio e outro ao final. Se o resultado é diferente do necesario, cambia os puntos de inicio e final.
Finalmente atoparemos o valor desexado e devolveremos verdadeiro, ou os puntos de inicio e final converxerán e devolverán falso.
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;
};
Agora todo está ben, a solución parece ser a óptima. Pero quen pode garantir que a matriz foi ordenada?
Que entón?
A primeira vista, poderiamos ordenar primeiro a matriz e despois usar a solución anterior. Pero como afectará isto ao tempo de execución?
O mellor algoritmo é a clasificación rápida con complexidade temporal O (Nlog (N)). Se o usamos na nosa solución óptima, cambiará o seu rendemento de O(N) a O(Nlog(N)). É posible atopar unha solución lineal cunha matriz non ordenada?
Solución 4
Complexidade temporal: O(N).
Complexidade espacial: O(N).
Si, hai unha solución lineal; para facelo, necesitamos crear unha nova matriz que conteña a lista de coincidencias que estamos a buscar. A compensación aquí é máis uso de memoria: é a única solución do documento cunha complexidade espacial maior que O(1).
Se o primeiro valor dunha matriz determinada é 1 e o valor de busca é 8, podemos engadir o valor 7 á matriz "valores de busca".
Despois, mentres procesamos cada elemento da matriz, podemos comprobar a matriz de "valores de busca" e ver se un deles é igual ao noso valor. Se si, devolve verdadeiro.
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;
};A base da solución é un bucle for, que, como vimos anteriormente, ten unha complexidade temporal lineal de O(N).
A segunda parte iterativa da nosa función é Array.prototype.include(), un método JavaScript que devolverá verdadeiro ou falso dependendo de se a matriz contén o valor indicado.
Para descubrir a complexidade temporal de Array.prototype.includes(), podemos ver o polyfill proporcionado por MDN (e escrito en JavaScript) ou usar un método no código fonte dun motor JavaScript como 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;
}
});
}Aquí a parte iterativa de Array.prototype.include() é o bucle while no paso 7 que (case) percorre toda a lonxitude da matriz dada. Isto significa que a súa complexidade temporal tamén é lineal. Ben, xa que sempre está un paso por detrás da nosa matriz principal, a complexidade temporal é O (N + (N - 1)). Usando a notación Big O, simplificámola a O(N), porque é N o que ten o maior impacto ao aumentar o tamaño da entrada.
En canto á complexidade espacial, necesítase unha matriz adicional cuxa lonxitude reflicta a matriz orixinal (menos un, si, pero que se pode ignorar), resultando en complexidade espacial O(N). Ben, o aumento do uso da memoria garante a máxima eficiencia do algoritmo.
Espero que che resulte útil o artigo como complemento da túa entrevista en vídeo. Mostra que un problema sinxelo pode resolverse de varias formas diferentes con diferentes cantidades de recursos empregados (tempo, memoria).
Skillbox recomenda:
- Curso online aplicado .
- Curso en liña .
- Curso práctico anual .
Fonte: www.habr.com