Cuando estaba estudiando el rendimiento de los algoritmos, me encontré con esto . No solo da una idea de cómo se realizan las entrevistas en las grandes corporaciones tecnológicas, sino que también permite comprender cómo se resuelven los problemas algorítmicos de la manera más eficiente posible.
Este artículo es una especie de acompañamiento del vídeo. En él proporciono comentarios sobre todas las soluciones mostradas, además de mi propia versión de la solución en JavaScript. También se discuten los matices de cada algoritmo.
Recordamos: para todos los lectores de "Habr": un descuento de 10 rublos al inscribirse en cualquier curso de Skillbox utilizando el código promocional "Habr".
Skillbox recomienda: Curso práctico .
Formulación del problema
Se nos da una matriz ordenada y un valor específico. Luego se le pide que cree una función que devuelva verdadero o falso dependiendo de si la suma de dos números cualesquiera en la matriz puede ser igual a un valor determinado.
En otras palabras, ¿hay dos números enteros en la matriz, x e y, que cuando se suman dan como resultado el valor especificado?
Ejemplo A
Si nos dan una matriz [1, 2, 4, 9] y el valor es 8, la función devolverá falso porque no hay dos números en la matriz que puedan sumar 8.
Ejemplo B
Pero si es una matriz [1, 2, 4, 4] y el valor es 8, la función debería devolver verdadero porque 4 + 4 = 8.
Solución 1: fuerza bruta
Complejidad del tiempo: O (N²).
Complejidad espacial: O(1).
El significado más obvio es utilizar un par de bucles anidados.
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 no es eficiente porque verifica cada suma posible de dos elementos en la matriz y también compara cada par de índices dos veces. (Por ejemplo, cuando i = 1 y j = 2 es en realidad lo mismo que comparar con i = 2 y j = 1, pero en esta solución probamos ambas opciones).
Debido a que nuestra solución utiliza un par de bucles for anidados, es cuadrática con complejidad temporal O(N²).
Solución 2: búsqueda binaria
Complejidad del tiempo: O (Nlog (N)).
Complejidad espacial: O (1).
Dado que las matrices están ordenadas, podemos buscar una solución mediante la búsqueda binaria. Este es el algoritmo más eficiente para matrices ordenadas. La búsqueda binaria en sí tiene un tiempo de ejecución de O (log (N)). Sin embargo, aún necesita usar un bucle for para comparar cada elemento con todos los demás valores.
Así es como podría ser una solución. Para aclarar las cosas, utilizamos una función separada para controlar la búsqueda binaria. Y también la función removeIndex(), que devuelve la versión de la matriz menos el índice dado.
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;
};El algoritmo comienza desde el índice [0]. Luego crea una versión de la matriz excluyendo el primer índice y utiliza la búsqueda binaria para ver si alguno de los valores restantes se puede agregar a la matriz para producir la suma deseada. Esta acción se realiza una vez para cada elemento de la matriz.
El bucle for en sí tendrá una complejidad temporal lineal de O(N), pero dentro del bucle for realizamos una búsqueda binaria, lo que da una complejidad temporal general de O(Nlog(N)). Esta solución es mejor que la anterior, pero todavía hay margen de mejora.
Solución 3: tiempo lineal
Complejidad del tiempo: O (N).
Complejidad espacial: O(1).
Ahora resolveremos el problema, recordando que la matriz está ordenada. La solución es tomar dos números: uno al principio y otro al final. Si el resultado difiere del requerido, cambie los puntos inicial y final.
Al final, encontraremos el valor deseado y devolveremos verdadero, o los puntos inicial y final convergerán y 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;
};
Ahora todo está bien, la solución parece óptima. ¿Pero quién puede garantizar que la matriz fue ordenada?
Entonces que
A primera vista, simplemente podríamos haber ordenado la matriz primero y luego usar la solución anterior. ¿Pero cómo afectará esto al tiempo de ejecución?
El mejor algoritmo es el de clasificación rápida con complejidad temporal O (Nlog (N)). Si lo usamos en nuestra solución óptima, cambiará su rendimiento de O(N) a O(Nlog(N)). ¿Es posible encontrar una solución lineal con una matriz desordenada?
Solución 4
Complejidad del tiempo: O (N).
Complejidad espacial: O (N).
Sí, existe una solución lineal; para hacer esto, necesitamos crear una nueva matriz que contenga la lista de coincidencias que estamos buscando. La compensación aquí es un mayor uso de memoria: es la única solución en el documento con una complejidad espacial mayor que O(1).
Si el primer valor de una matriz determinada es 1 y el valor de búsqueda es 8, podemos agregar el valor 7 a la matriz de "valores de búsqueda".
Luego, a medida que procesamos cada elemento de la matriz, podemos verificar la matriz de "valores de búsqueda" y ver si uno de ellos es igual a nuestro valor. En caso afirmativo, devuelva verdadero.
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 de la solución es un bucle for que, como vimos anteriormente, tiene una complejidad temporal lineal de O(N).
La segunda parte iterativa de nuestra función es Array.prototype.include(), un método JavaScript que devolverá verdadero o falso dependiendo de si la matriz contiene el valor dado.
Para determinar la complejidad temporal de Array.prototype.includes(), podemos mirar el polyfill proporcionado por MDN (y escrito en JavaScript) o usar un método en el código fuente de un 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í, la parte iterativa de Array.prototype.include() es el bucle while del paso 7 que (casi) atraviesa toda la longitud de la matriz dada. Esto significa que su complejidad temporal también es lineal. Bueno, dado que siempre está un paso por detrás de nuestra matriz principal, la complejidad temporal es O (N + (N - 1)). Usando la notación O grande, la simplificamos a O(N), porque es N el que tiene el mayor impacto al aumentar el tamaño de entrada.
Con respecto a la complejidad espacial, se necesita una matriz adicional cuya longitud refleje la matriz original (menos uno, sí, pero eso puede ignorarse), lo que da como resultado una complejidad espacial O(N). Bueno, un mayor uso de la memoria garantiza la máxima eficiencia del algoritmo.
Espero que el artículo le resulte útil como complemento de su entrevista en vídeo. Muestra que un problema simple se puede resolver de varias maneras diferentes con diferentes cantidades de recursos utilizados (tiempo, memoria).
Skillbox recomienda:
- Curso en línea aplicado .
- Curso por Internet .
- curso práctico anual .
Fuente: habr.com