Estrutura de dados, para que servem e por que tão temidas?

As estruturas de dados nada mais são do que formas para armazenar dados na memória, as formas de armazenamento podem variar, podendo ser tanto de maneira sequencial ou não, como é o caso de uma estrutura falada mais a frente.

Mas afinal, o que isso muda, entre usar um array ou uma lista ligada, um set ou um map?

Basicamente, o que muda é o tempo de busca e inserção em cada uma das estruturas de dados, mas por que isso é importante? Bom, imagine você ter 1 milhão de itens aleatórios e precisa encontrar um item em específico, o que seria necessário para encontrar o mesmo? Bom no pior caso, seria necessário passar por todos os itens para encontrar o alvo, mas no melhor caso, talvez o primeiro item seja o alvo.

Foi citado anteriormente o melhor caso e o pior caso, mas existe ainda o caso médio, ambos casos nada mais são do que uma forma de mensurar o funcionamento de um algoritmo de busca, inserção ou exclusão, usamos uma notação chamada notação assintótica para podermos mensurar a velocidade de um algoritmo.

Notação assintótica – Complexidade de Tempo e Espaço

É a forma de mensurar o funcionamento de um algoritmo conforme a entrada de dados aumenta. Além de entender por debaixo dos panos os códigos adicionados ao projeto. Aqui são alguns exemplos dos tempos mais comuns encontrados nos algoritmos do dia a dia.

Imagem retirada do livro Grokking Algorithms..

Importante observar que os números não são exatos, é apenas uma exemplo abstrato para facilitar o entendimento.

Sendo O (1) um tempo constante, equivalente a como se você soubesse exatamente onde buscar este valor na memória. O(N) seria quando você precisar visitar todos os itens.

Perceba que, quanto mais complexo o código é, mais tempo será levado para para chegar ao resultado esperado.

Um algoritmo de O(N log N) é basicamente quando é passado por cada item dentro de uma lista e após isso, é feito uma busca binária.

Mas o que seria uma busca binária? Busca binária é um algoritmo muito importante da ciência da computação, utilizado para otimizar diversos algoritmos.

Basicamente com o uso da busca binária, podemos diminuir o número de tentativas para achar um valor. Mas aqui vai uma observação importante, é necessário que os mesmos itens estejam ordenados, não necessariamente de maneira sequencial. A busca binária funciona da seguinte forma. Imagine que você tem está procurando o número 8, numa lista de 20 itens, em cada tentativa de achar o número, é dividido na metade o número de itens, ou seja, se no começo era 20, na próxima tentativa passa a ser 10, e então 5 e assim por diante.

Segue um vídeo demonstrando de maneira interativa uma implementação de busca binária. Lembrando que pode haver ainda variações dependendo da solução do resultado esperado.

N² é basicamente quando para cada item é necessário percorrer todos os outros, exemplo, de 5 itens, seria necessário percorrer os itens 32 vezes.

É importantíssimo masterizar a forma de resolver de maneira mais otimizada possível, é muito falado em escalabilidade, alta disponibilidade, paralelismo etc. e muitas vezes, o código é negligenciado. O que resulta em frustração do usuário ou mesmo dos desenvolvedores que mesmo com uma boa arquitetura enfrentam problemas de lentidão, muitas vezes causado pela negligência da complexidade dos códigos escritos no dia a dia.

Existem diversos sites que disponibilizam problemas que podem ser resolvidos de maneira otimizada com as estruturas corretas, as FAANG’s (acrônimo utilizado para referenciar as empresas gigantes de tecnologia- Facebook, Amazon, Apple, Netflix e Google) são conhecidas por seus processos onde este conhecimento é cobrado em suas entrevistas técnicas.

Imagine o seguinte problema:

Dado um array de números inteiros e um alvo inteiro, retorna os índices dos dois números de forma que eles se somam ao alvo. Você pode presumir que cada entrada teria exatamente uma solução e não pode usar o mesmo elemento duas vezes.

Exemplo 1:

Entradas: nums = [2,7,11,15], target = 9
Saída: [0,1]
Saída: Dado que nums[0] + nums[1] == 9, retornamos [0, 1].

Exemplo 2:

Entrada: nums = [3,2,4], target = 6
Saída: [1,2]

De maneira intuitiva, pensaríamos em resolver da seguinte forma, está é uma maneira não otimizada, comumente chamado de bruta força.

// Time complexity: O(n^2)
private static int[] findTwoSum_BruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }
    return new int[] {};
}

Este seria a maneira mais otimizada de resolver o problema. É uma maneira que é necessário um pouco mais de esforço para encontrar a solução, entretanto, esta solução é consideravelmente mais rápida que a primeira, ainda mais se considerarmos grande entrada de dados, agora imagine diversos usuários requisitando o uso dessa API.

// Time complexity: O(n)
private static int[] findTwoSum(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (numMap.containsKey(complement)) {
            return new int[] { numMap.get(complement), i };
        } else {
            numMap.put(nums[i], i);
        }
    }
    return new int[] {};
}

Este é um exemplo de uso de uma estrutura de dados conhecida como HashMap, Map ou Dictionaries para otimizar a solução, diminuindo consideravelmente o tempo de resposta.

Este artigo teve o intuito de introduzir de maneira simples os conceitos importantes para entendermos as estruturas gerais. Os casos de uso e complexidade das estruturas mais usadas serão discutidos e apresentados em outros posts. Os conceitos aqui apresentados são estudados na ciência da computação, busquei simplificar o máximo para o melhor entendimento.