Quando eu estava estudando o desempenho de algoritmos, me deparei com isso . Ele não apenas dá uma ideia de como as entrevistas são conduzidas em grandes corporações de tecnologia, mas também permite entender como os problemas algorítmicos são resolvidos da maneira mais eficiente possível.
Este artigo é uma espécie de acompanhamento do vídeo. Nele forneço comentários sobre todas as soluções mostradas, além da minha própria versão da solução em JavaScript. As nuances de cada algoritmo também são discutidas.
Lembramos: para todos os leitores de "Habr" - um desconto de 10 rublos ao se inscrever em qualquer curso Skillbox usando o código promocional "Habr".
A Skillbox recomenda: curso prático .
Formulação do problema
Recebemos um array ordenado e um valor específico. Em seguida, é solicitado que crie uma função que retorne verdadeiro ou falso, dependendo se a soma de quaisquer dois números na matriz pode ser igual a um determinado valor.
Em outras palavras, existem dois inteiros na matriz, xey, que quando somados são iguais ao valor especificado?
Exemplo A
Se recebermos um array [1, 2, 4, 9] e o valor for 8, a função retornará falso porque não há dois números no array que possam somar 8.
Exemplo B
Mas se for um array [1, 2, 4, 4] e o valor for 8, a função deverá retornar verdadeiro porque 4 + 4 = 8.
Solução 1: Força bruta
Complexidade de tempo: O(N²).
Complexidade espacial: O(1).
O significado mais óbvio é usar um par de loops aninhados.
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 solução não é eficiente porque verifica todas as somas possíveis de dois elementos no array e também compara cada par de índices duas vezes. (Por exemplo, quando i = 1 e j = 2 é na verdade o mesmo que comparar com i = 2 e j = 1, mas nesta solução tentamos as duas opções).
Como nossa solução usa um par de loops for aninhados, ela é quadrática com complexidade de tempo O(N²).
Solução 2: pesquisa binária
Complexidade de tempo: O(Nlog(N)).
Complexidade do espaço: O(1).
Como as matrizes são ordenadas, podemos procurar uma solução usando a pesquisa binária. Este é o algoritmo mais eficiente para matrizes ordenadas. A própria pesquisa binária tem um tempo de execução de O(log(N)). No entanto, você ainda precisa usar um loop for para verificar cada elemento em relação a todos os outros valores.
Esta é a aparência de uma solução. Para deixar as coisas claras, usamos uma função separada para controlar a pesquisa binária. E também a função removeIndex(), que retorna a versão do array menos o índice fornecido.
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 começa no índice [0]. Em seguida, ele cria uma versão do array excluindo o primeiro índice e usa a pesquisa binária para ver se algum dos valores restantes pode ser adicionado ao array para produzir a soma desejada. Esta ação é executada uma vez para cada elemento do array.
O loop for em si terá uma complexidade de tempo linear de O(N), mas dentro do loop for realizamos uma pesquisa binária, o que fornece uma complexidade de tempo geral de O(Nlog(N)). Esta solução é melhor que a anterior, mas ainda há espaço para melhorias.
Solução 3: tempo linear
Complexidade de tempo: O(N).
Complexidade espacial: O(1).
Agora vamos resolver o problema, lembrando que o array está ordenado. A solução é pegar dois números: um no início e outro no final. Se o resultado for diferente do desejado, altere os pontos inicial e final.
Eventualmente encontraremos o valor desejado e retornaremos verdadeiro, ou os pontos inicial e final convergirão e retornarão 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 está tudo bem, a solução parece ótima. Mas quem pode garantir que o array foi ordenado?
O que então?
À primeira vista, poderíamos simplesmente ter ordenado o array primeiro e depois usado a solução acima. Mas como isso afetará o tempo de execução?
O melhor algoritmo é o quicksort com complexidade de tempo O (Nlog (N)). Se o usarmos em nossa solução ideal, seu desempenho mudará de O(N) para O(Nlog(N)). É possível encontrar uma solução linear com um array não ordenado?
Solução 4
Complexidade de tempo: O(N).
Complexidade do espaço: O(N).
Sim, existe uma solução linear; para fazer isso, precisamos criar um novo array contendo a lista de correspondências que procuramos. A compensação aqui é mais uso de memória: é a única solução no artigo com complexidade de espaço maior que O(1).
Se o primeiro valor de um determinado array for 1 e o valor de pesquisa for 8, podemos adicionar o valor 7 ao array "valores de pesquisa".
Então, à medida que processamos cada elemento do array, podemos verificar o array de “valores de pesquisa” e ver se um deles é igual ao nosso valor. Se sim, retorne 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 solução é um loop for, que, como vimos acima, possui uma complexidade de tempo linear de O(N).
A segunda parte iterativa de nossa função é Array.prototype.include(), um método JavaScript que retornará verdadeiro ou falso dependendo se o array contém o valor fornecido.
Para descobrir a complexidade de tempo de Array.prototype.includes(), podemos observar o polyfill fornecido pelo MDN (e escrito em JavaScript) ou usar um método no código-fonte de um mecanismo JavaScript como o 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;
}
});
}Aqui, a parte iterativa de Array.prototype.include() é o loop while na etapa 7 que (quase) percorre todo o comprimento do array fornecido. Isso significa que sua complexidade de tempo também é linear. Bem, como está sempre um passo atrás do nosso array principal, a complexidade do tempo é O (N + (N - 1)). Usando a notação Big O, simplificamos para O(N) - porque é N que tem o maior impacto ao aumentar o tamanho da entrada.
Em relação à complexidade espacial, é necessário um array adicional cujo comprimento espelhe o array original (menos um, sim, mas isso pode ser ignorado), resultando em O(N) complexidade espacial. Bem, o aumento do uso de memória garante a máxima eficiência do algoritmo.
Espero que você considere o artigo útil como complemento à sua entrevista em vídeo. Mostra que um problema simples pode ser resolvido de diversas maneiras com diferentes quantidades de recursos utilizados (tempo, memória).
A Skillbox recomenda:
- Curso on-line aplicado .
- Curso online .
- curso de ano prático .
Fonte: habr.com
