Quando eu estava estudando o desempenho de algoritmos, me deparei com
este vídeo da falsa entrevista do Google . Ele não apenas fornece uma idéia de como as entrevistas são realizadas em grandes empresas de tecnologia, mas também permite que você entenda como os problemas algorítmicos são resolvidos e com mais eficiência.
Este artigo é um tipo de acompanhamento para o vídeo. Nele, faç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 que: para todos os leitores de "Habr" - um desconto de 10.000 rublos ao se inscrever em qualquer curso Skillbox usando o código promocional "Habr".
A Skillbox recomenda: Curso prático "Mobile Developer PRO" .
Declaração do problema
Nos é dado um array ordenado e um valor específico. Em seguida, eles pedem para criar uma função que retorne verdadeiro ou falso, dependendo se a soma de quaisquer dois números da matriz pode ser igual ao valor fornecido.
Em outras palavras, existem dois números inteiros xey na matriz que, quando adicionados, são iguais ao valor especificado?
Exemplo ASe nos foi dado um array [1, 2, 4, 9] e um valor de 8, a função retornará false, porque nenhum número da matriz pode dar 8 no total.
Exemplo BMas se for uma matriz [1, 2, 4, 4] e o valor for 8, a função retornará true, porque 4 + 4 = 8.
Solução 1. BruteforceDificuldade temporal: 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; };
Essa solução não pode ser considerada eficaz, pois verifica todas as somas possíveis de dois elementos na matriz e também compara cada par de índices duas vezes. (Por exemplo, quando i = 1 ej = 2 - na verdade, é o mesmo que comparar com i = 2 ej = 1, mas nesta solução tentamos as duas opções).
Como nossa solução usa um par de aninhados para loops, ela é quadrática com uma complexidade de tempo de O (N²).
Solução 2. Pesquisa binária (binária)Dificuldade temporal: O (Nlog (N)).
Complexidade espacial: 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 possui um tempo de execução O (log (N)). No entanto, você ainda precisa usar um loop for para verificar cada elemento em relação a todos os outros valores.
Aqui está a aparência da solução. Para esclarecer tudo, usamos uma função separada para controlar a pesquisa binária. Assim como a função removeIndex (), que retorna a versão da matriz menos o índice especificado.
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 da matriz, excluindo o primeiro índice, e usa uma pesquisa binária para verificar se algum dos valores restantes pode ser adicionado à matriz para obter a quantidade desejada. Esta ação é executada uma vez para cada elemento na matriz.
O loop for em si terá uma complexidade de tempo linear de O (N), mas dentro do loop for realizamos uma pesquisa binária, que fornece a complexidade de tempo total de O (Nlog (N)). Esta solução é melhor que a anterior, mas ainda há algo a melhorar.
Solução 3. Tempo linearDificuldade temporal: O (N).
Complexidade espacial: O (1).Agora vamos resolver o problema, lembrando que a matriz está classificada. A solução é pegar dois números: um no começo e outro no final. Se o resultado for diferente do necessário, alteramos os pontos inicial e final.
No final, atingimos o valor desejado e retornamos true, ou os pontos inicial e final convergem e retornam 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; };
Agora está tudo bem, a solução parece ser ótima. Mas quem garantirá que a matriz foi encomendada?
O que então?
À primeira vista, poderíamos apenas classificar a matriz primeiro e depois usar a solução acima. Mas como isso afetará o tempo de execução?
O melhor algoritmo é a classificação rápida com complexidade de tempo O (Nlog (N)). Se o usarmos em nossa solução ideal, ele mudará seu desempenho de O (N) para O (Nlog (N)). É possível encontrar uma solução linear com uma matriz não ordenada?
Decisão 4Dificuldade temporal: O (N).
Complexidade espacial: O (N).Sim, existe uma solução linear, para isso você precisa criar uma nova matriz contendo uma lista de correspondências que estamos procurando. A desvantagem aqui é o uso mais ativo da memória: esta é a única solução no artigo com complexidade espacial superior a O (1).
Se o primeiro valor dessa matriz for 1 e o valor da pesquisa for 8, podemos adicionar o valor 7 à matriz dos "valores da pesquisa".
Depois, processando cada elemento da matriz, podemos verificar a matriz dos "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 é o loop for, que, como vimos acima, possui complexidade de tempo linear O (N).
A segunda parte da iteração de nossa função é Array.prototype.include (), um método JavaScript que retornará verdadeiro ou falso, dependendo de a matriz conter o valor especificado.
Para descobrir a complexidade de tempo de Array.prototype.includes (), podemos examinar 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 ++).
Aqui, a parte iterativa de Array.prototype.include () é o loop while na etapa 7, que (quase) atravessa todo o comprimento da matriz especificada. Isso significa que sua complexidade temporal também é linear. Bem, como está sempre um passo atrás da nossa matriz principal, a complexidade do tempo é O (N + (N - 1)). Usando a notação O grande, simplificamos para O (N) - porque é N que tem a maior influência com o aumento do tamanho da entrada.
Quanto à complexidade espacial, é necessária uma matriz adicional, cujo comprimento reflete a matriz original (menos uma, sim, mas isso pode ser ignorado), o que leva à complexidade espacial de O (N). Bem, o aumento do uso de memória garante a máxima eficiência do algoritmo.
Espero que este artigo seja útil para você como anexo de uma entrevista em vídeo. Isso mostra que um problema simples pode ser resolvido de várias maneiras diferentes, com diferentes quantidades de recursos utilizados (tempo, memória).
A Skillbox recomenda: