Algoritmos e como analisar sua complexidade

Algoritmos estão envolvidos em quase todas as tarefas que realizamos diariamente. Nós executamos muitos deles em "automático", sem sequer perceber "para que" eles são usados ​​ou "como" os usamos. No desenvolvimento de software, não é tão diferente. Mas, de qualquer maneira, quais são os algoritmos? E por que é importante analisar sua complexidade?

Vamos descobrir! :)

O que é um algoritmo?

Um conjunto de etapas necessárias para executar uma tarefa.

Programas de computador não são as únicas coisas que executam algoritmos, eles também são executados e implementados por nós, humanos.

Por exemplo, você pensou no algoritmo que executa as seguintes tarefas?

  • Escove seus dentes
  • Tome um banho
  • cozinhar
  • Dirija para trabalhar em casa

No nosso dia-a-dia, executamos uma série de etapas para concluir pelo menos uma das tarefas mencionadas acima. Vamos usar a tarefa de dirigir para trabalhar em casa como um exemplo. Os passos que tomo são basicamente os seguintes:

  1. Entre no meu carro
  2. Dirija até a casa de um amigo para dar uma volta
  3. Dirija para o escritório onde trabalho
  4. Estacione meu carro na garagem

Este é o conjunto de etapas (algoritmo) que preciso executar para concluir esta tarefa.

Agora, pense no conjunto de etapas necessárias para executar a mesma tarefa. É provável que eles sejam um pouco diferentes dos meus. Nossos algoritmos podem ser diferentes, mas nosso objetivo é o mesmo.

Os programas de computador não são muito diferentes: há uma variedade de algoritmos que podem ser usados ​​para realizar uma série de tarefas. Frequentemente, não nos preocupamos com o que são, simplesmente os usamos (inclusive eu).

Por exemplo, como deve ser o algoritmo usado pelo Waze e pelo Google Maps, aquele que calcula a melhor rota entre dois locais? E o algoritmo da Netflix que sugere filmes e séries com base no que você assistiu?

Pessoalmente, eu não poderia lhe dizer. No entanto, eu sei que eles são eficientes. E eficiência é o padrão que usamos para analisar a complexidade de um algoritmo.

O que é complexidade de algoritmo?

Na ciência da computação, a complexidade do algoritmo refere-se a quanto tempo e espaço um algoritmo consome para executar uma tarefa, de acordo com o tamanho de sua entrada.

Geralmente, os algoritmos são avaliados pelo consumo de tempo e espaço, mas vou abordar apenas a complexidade do tempo neste post.

Analisar a complexidade do tempo nos permite determinar como um algoritmo se comportará, com um aumento em seus elementos de entrada. Podemos ter uma idéia do tempo necessário para processar 10, 100 ou 1000 elementos.

E por que essa análise é importante?

  • Determinar qual algoritmo é mais eficiente;
  • Ser capaz de desenvolver algoritmos mais eficientes;
  • Ser capaz de analisar se a biblioteca de um algoritmo, ou mesmo sua linguagem real, é eficiente.

Para resumir, a eficiência é o ponto!

Complexidade temporal

O tempo que leva para uma atividade ser concluída.

Podemos começar a analisar o tempo com o método Frequency Count, que basicamente conta o número de vezes que uma instrução da máquina é executada. Cada etapa (instrução) recebe uma unidade de tempo, começando com 1.

O tempo que o algoritmo consome é expresso pela função f (n), em que n representa o tamanho dos dados.

O resultado de uma análise é expresso da seguinte forma:

([função que expressa o tempo]) = [soma das unidades de tempo]

Agora vamos analisar alguns algoritmos para entender como isso funciona na realidade.

A primeira função adiciona dois números inteiros:

Podemos ver que, para essa tarefa, o algoritmo implementado executa apenas uma única etapa: a soma de dois números. Como atribuímos um valor para cada etapa, o resultado é f (n) = 1.

Vejamos o próximo exemplo, que é um algoritmo que divide um número inteiro por outro número inteiro:

Apesar de ser uma operação matemática semelhante à soma, o algoritmo contém mais etapas, pois precisa verificar se o divisor é 0; se for esse o caso, a divisão não será realizada. Como temos quatro etapas no total, e a cada uma delas é atribuído um valor de 1, o resultado é f (n) = 4.

O próximo algoritmo resume todos os elementos de uma lista de números inteiros:

Nesse algoritmo, uma das etapas inclui para, uma instrução para repetição; isso significa que o código dentro de for será executado várias vezes. Como o número de execuções depende do tamanho dos dados, atribuímos o valor de n como uma unidade de tempo. O resultado é f (n) = 2n + 3.

O próximo algoritmo adiciona a soma de uma lista com a soma de uma segunda lista.

Como resultado, temos f (n) = 2n² + 2n + 3.

Até o momento, vimos apenas algoritmos simples, certo? Agora imagine analisar algoritmos mais complexos e precisar executar esses cálculos? Não é muito viável, é? Embora pareça o mais apropriado, é muito trabalhoso e, no final das contas, não vale a pena.

Normalmente, quando analisamos um algoritmo, estamos tentando descobrir seus comportamentos quando há muitos elementos a serem processados. É nessas situações que precisamos encontrar o termo predominante da soma das unidades de tempo.

Por exemplo, qual é o termo predominante da soma do terceiro algoritmo?

f (n) = 2n + 3

Nesse caso, o termo predominante em 2 * n, e eu explicarei o porquê!

Em qualquer situação em que n seja maior que 1 (n> 1), o produto (o resultado da multiplicação) já valerá mais do que o segundo termo da soma.

Teste algo: substitua n por um número inteiro maior que 1 e faça a multiplicação.

E o termo predominante da soma do último algoritmo?

f (n) = 2n² + 2n + 3

Nesse caso, o termo predominante é 2 * n², porque quando n> 1, o produto sempre será maior que o segundo e o terceiro termos da soma. Vá em frente, teste!

Portanto, existe uma maneira mais comum, por assim dizer, de analisar a complexidade dos algoritmos, onde constantes e termos menos significativos são desconsiderados. Esse método é chamado de Complexidade Assintótica.

É aqui que a Ordem da Complexidade entra em cena, também conhecida como Notação-O ou Big-O.

Notação Big-O

Usado para classificar um algoritmo considerando a taxa de crescimento das operações à medida que o número de elementos processados ​​aumenta.

A notação Big-O também define uma função que expressa a complexidade do tempo de um algoritmo. Para esse fim, n é usado como uma função da letra O.

As classes mais comuns são:

  • O (1) - Constante, o número de operações não aumenta à medida que o número de elementos aumenta
  • O (log n) - Logarítmico, o número de operações é menor que o número de elementos
  • O (n) - Linear, o número de operações aumenta proporcionalmente ao número de elementos
  • O (n²) Quadrático, o número de operações será maior que o número de elementos
  • O (2 ^ n) - Exponencial, o número de operações aumenta rapidamente em comparação com o número de elementos
  • O (n!) - Fatorial, o número de operações aumenta muito, muito rapidamente, mesmo para um pequeno número de elementos

Abaixo, temos um gráfico que ilustra a taxa de crescimento das operações x quantidade de elementos:

O gráfico é classificado da seguinte forma:

  • Zona vermelha é terrível, evite-o!
  • Zona laranja é ruim, evite-o também!
  • Zona amarela é justa, razoável!
  • Zona verde-clara é boa, legal!
  • Zona verde-escura é excelente, parabéns!

Agora, usaremos a notação Big-O para categorizar os algoritmos mencionados anteriormente, sempre usando o termo predominante para nos guiar.

O primeiro algoritmo resultou em f (n) = 1; significando que, independentemente do aumento de elementos, o algoritmo executa apenas uma operação. Assim, podemos classificar o algoritmo como Constante - O (1).

O segundo algoritmo resultou em f (n) = 4; significando que, independentemente do aumento de elementos, o algoritmo executará quatro operações. Assim, também podemos classificar esse algoritmo como Constante - O (1).

O resultado do terceiro algoritmo foi f (n) = 2n + 3; significando que o número de operações aumentará proporcionalmente ao número de elementos, visto que n serve como uma variável nessa função. Assim, podemos definir esse algoritmo como Linear - O (n).

O resultado do último algoritmo resultou em f (n) = 2n² + 2n + 3, significando que o número de operações aumentará mais que o número de elementos. Nesse caso, n também serve como variável, mas é elevado à segunda potência (ao quadrado). Assim, podemos definir esse algoritmo como Quadratic - O (n²).

A tabela abaixo ilustra o crescimento do número de operações no que se refere ao crescimento do número de elementos.

Observe que em um algoritmo exponencial, 16 elementos resultariam em pelo menos 65,5536 operações. Muito perturbador, certo?

Em geral, o processo de análise é o mesmo que temos feito: contando o número de etapas e identificando o termo predominante.

Algumas tendências que podemos observar:

  • Algoritmos que não possuem um loop de repetição tendem a ser Constantes - O (1)
  • Algoritmos que possuem loops de repetição, desde que não estejam aninhados, tendem a ser Lineares - O (n)
  • Algoritmos que possuem dois loops de repetição aninhados tendem a ser quadráticos - O (n²)
  • O acesso direto ao índice de uma matriz é geralmente O (1) (constante)
  • Os métodos de extensão de lista, em média, são O (n). Por exemplo: any, sum e filter.
  • Algoritmos de classificação como Bubble Sort, Insertion Sort e Selection Sort são geralmente O (n²).

Saber classificar algoritmos nos dá a capacidade de julgar a eficiência ou ineficiência de um algoritmo. Obviamente, não podemos medir o tempo exato de execução em segundos, minutos ou horas. Para fazer isso, ele precisa ser executado, medido e alterado de acordo. Imagine fazer isso para algoritmos que levam horas ou até dias para serem executados? Sem chance!

Espero ter cumprido o objetivo deste post, que foi fornecer uma visão geral dos algoritmos e suas análises usando os métodos Frequency Count e Big-O.

Deixei algumas referências abaixo como material de leitura adicional!

Referências:

Vídeos 1 a 1,7

Deseja trazer inovação ao mercado de empréstimos por meio da tecnologia? Estamos sempre procurando novas pessoas para se juntar à nossa equipe!

Confira nossas vagas aqui.