Executando verificação de segurança...
2
lucasrguerra
2 min de leitura ·

[DÚVIDA] Cálculo de complexidade de um algoritmo

Olá, tudo bem?

Recetemente eu estava estudando na disciplina de Algoritmos e Estruturas de Dados e desenvolvi 2 algoritmos como atividade prática. O primeiro é o Two Sum, que busca 2 números em 1 array que quando somados são iguais ao "target_number". O segundo é uma evolução do anterior, o Three Sum, faz exatamente a mesma coisa que o anterior, porém dessa vez com 3 números, com o diferencial de retornar todas as possibilidades.

Código do Two Sum:

function getTwoSum(numbers, target_sum) {
  const repeat_1 = numbers.length - 1;
  const numbers_length = numbers.length;
  for (let index_1 = 0; index_1 < repeat_1; index_1++) {
    const number_1 = numbers[index_1];
    const outher_numbers = numbers.slice(index_1 + 1, numbers_length);
    const repeat_2 = outher_numbers.length;
    
    for (let index_2 = 0; index_2 < repeat_2; index_2++) {
      const number_2 = outher_numbers[index_2];
      const sum = number_1 + number_2;
      if (sum === target_sum) {
        return [number_1, number_2];
      };
    };
  };

  return [];
}

Código do Three Sum:

function getThreeSum(numbers, target_sum) {
  const valid_numbers = [];
  const repeat_1 = numbers.length - 1;
  const numbers_length = numbers.length;
  for (let index_1 = 0; index_1 < repeat_1; index_1++) {
    const number_1 = numbers[index_1];
    const other_numbers_1 = numbers.slice(index_1 + 1, numbers_length);
    const repeat_2 = other_numbers_1.length - 1;
    
    for (let index_2 = 0; index_2 < repeat_2; index_2++) {
      const number_2 = other_numbers_1[index_2];
      const other_numbers_2 = other_numbers_1.slice(index_2 + 1, numbers_length);
      const repeat_3 = other_numbers_2.length;

      for (let index_3 = 0; index_3 < repeat_3; index_3++) {
        const number_3 = other_numbers_2[index_3];
        const sum = number_1 + number_2 + number_3;
        if (sum === target_sum) {
          valid_numbers.push([number_1, number_2, number_3].sort());
        };
      };
    };
  };

  return valid_numbers;
}

Ambos funcionam super bem, porém eu gostaria de saber qual é a complexidade de cada um, pois vi outros companheiros de turma utilizando o método Array.prototype.includes(), porém esse método é de complexidade O(n), o que faria a função getTwoSum por exemplo ter uma complexidade O(n²), já que tem o O(n) do loop For e o O(n) do método includes().

Porém na forma que eu implementei, fica algo menos complexo que O(n²) mas ao mesmo tempo não fica tão simples quanto o O(n). Vocês podem me ajudar a calcular a complexidade?

Carregando publicação patrocinada...
1
kht

O getTwoSum tem complexidade O(n2). Lembre-se que a notação Big-O é assintótica (de forma bem resumida, é como se você "arredondasse" para a grandeza mais próxima). E como vc faz dois loops aninhados no mesmo array, na prática é quadrático. Mesmo que o loop interno não percorra todos os elementos, o valor será mais próximo do quadrático do que do linear (considerando valores grandes, já que Big-O define o "limite quando N tende ao infinito").

Vale contar que cada chamada de slice percorre um trecho do array novamente, para poder criar outro (ou seja, vc está criando vários arrays, um novo a cada iteração de index_1). Quer dizer que para cada elemento, vc cria um novo sub-array e depois faz um loop no array retornado. Então para cada elemento, é como se vc percorresse o array duas vezes: uma para o slice criar outro array, e outra para percorrer os elementos do array que slice retornou (n * 2n, ou seja, 2n2), mas como a notação é assintótica, continua sendo O(n2).

Enfim, não precisa de slice, pois não há motivo para copiar parte do array. Afinal em nenhum momento vc modifica o array (que seria um motivo válido para fazer a cópia, por exemplo), e não há problema nenhum se os dois loops usarem o mesmo array. Ou seja, pode fazer o loop interno no mesmo array, basta começar no i + 1:

function getTwoSum(numbers, target_sum) {
    for (let i = 0; i < numbers.length - 1; i++) {
        for (let j = i + 1; j < numbers.length; j++) {
            if (numbers[i] + numbers[j] === target_sum) {
                return [numbers[i], numbers[j]];
            }
        }
    }

    return [];
}

Note que depois das } não precisa de ponto-e-vírgula.

Claro, continua sendo quadrático, mas agora com menos iterações, porque sem slice não há a criação de novos arrays (agora é n2 em vez de 2n2, mas ainda sim, a complexidade continua sendo O(n2)).

Da mesma forma, getThreeSum é O(n3), e não precisa de slice, pois com isso vc cria vários arrays desnecessariamente. Outra diferença é que no getTwoSum vc retorna assim que encontra um caso que sirva, enquanto no getThreeSum vc guarda todas as combinações possíveis, além de ordenar o resultado (mas pelo que entendi, era essa a intenção).

E outro detalhe é que vc chama sort em um array de números, mas assim ele não ordena corretamente, porque primeiro ele converte os números para string e a ordenação fica errada (faça o teste, rode console.log([3, 10, 2].sort()) pra ver o que acontece). Então precisa de um pequeno ajuste:

function getThreeSum(numbers, target_sum) {
    const result = [];
    for (let i = 0; i < numbers.length - 2; i++) {
        for (let j = i + 1; j < numbers.length - 1; j++) {
            for (let k = j + 1; k < numbers.length; k++) {
                if (numbers[i] + numbers[j] + numbers[k] === target_sum) {
                    // sort: para ordenar de acordo com o valor numérico, precisa desta função de callback
                    result.push([numbers[i], numbers[j], numbers[k]].sort((a, b) => a - b));
                }
            }
        }
    }
    return result;
}

E só para constar, existem algoritmos para reduzir getTwoSum para O(n) e getThreeSum para O(n2) (retirados respectivamente daqui e daqui):

function getTwoSum(numbers, target_sum) {
    let hashMap = {};
    for (let i = 0; i < numbers.length; i++) {
        if (hashMap[numbers[i]]) {
            return [hashMap[numbers[i]], numbers[i]];
        } else {
            hashMap[target_sum - numbers[i]] = numbers[i];
        }
    }
    return [];
}

function getThreeSum(numbers, target_sum) {
    const result = [];
    for (let i = 0; i < numbers.length - 2; i++) {
        // verifica no intervalo [i+1..n-1] se existe uma soma igual a target_sum - numbers[i]
        let s = new Set(); // usa um Set, que é O(1) para buscas
        let curr_sum = target_sum - numbers[i];
        for (let j = i + 1; j < numbers.length; j++) {
            if (s.has(curr_sum - numbers[j])) { // em um Set, a busca é O(1)
                result.push([numbers[i], numbers[j], curr_sum - numbers[j]].sort((a, b) => a - b));
            }
            s.add(numbers[j]);
        }
    }
    return result;
}

Ou, se quiser que getTwoSum retorne todas as possibilidades:

function twoSum(numbers, target_sum) {
    let hashMap = {}, results = [];
    for (let i = 0; i < numbers.length; i++) {
        if (hashMap[numbers[i]]) {
            results.push([hashMap[numbers[i]], numbers[i]].sort((a, b) => a - b));
        } else {
            hashMap[target_sum - numbers[i]] = numbers[i];
        }
    }
    return results;
}
1
lucasrguerra
Autor
Autor

Que massa!!! Até a leitura do código ficou muito melhor seguindo a técnica do i + 1 que você apresentou.

Admito que eu não sabia que em Big O eu deveria "arredondar" para a grandeza mais próxima, realmente muito bacana todo esse conhecimento a respeito da complexidade dos algoritmos, principalmente visando construir algoritmos cada vez mais eficientes, mas também para compreender como os algortimos que já temos funciona e como podemos melhorar eles. Tem sido extremamente interessante estudar esta área da computação e tenho ficado cara vez mais maravilhado com seus conceitos e regras.

Você realmente me ajudou um monte! E o artigo na Wiki que você sitou é realmente uma leitura muito massa pra quem tá querendo entender o que exatamente e o Big O. Realmente espetacular!

1