Published on

Introdução a Design de Algoritmos

Authors

Introdução

Nas atividades do dia-a-dia realizamos dezenas de tarefas. Muitas vezes, pouco paramos para observar em detalhes o que realizamos em cada atividade. Lavar a louça, arrumar a cama do quarto, varrer a casa, preparar um ovo cozido, dentre outras. Dessas atividades que comentei, você pode ter lembrado de algo que fez no dia de hoje, os passos para realizar essa(s) tarefa(s). Podemos descrever esses passos, como um algoritmo. Esse artigo foi inspirado e baseado em todas as referências descritas.

O que é um Algoritmo ?

Na definição formal no contexto lógico, no dicionário de Oxford a definição de algoritmo é:

um conjunto de regras que devem ser seguidas para resolver um problema específico.

No Dicionário Brasileiro da Língua Portuguesa, a definição é um pouco mais completa, ainda na perspectiva lógica:

Conjunto das regras de operação (conjunto de raciocínios) cuja aplicação permite resolver um problema enunciado por meio de um número finito de operações; pode ser traduzido em um programa executado por um computador, detectável nos mecanismos gramaticais de uma língua ou no sistema de procedimentos racionais finito, utilizado em outras ciências, para resolução de problemas semelhantes.

Temos também, definições na visão matemática de algoritmos, no qual informa que é:

Operação ou processo de cálculo; sequência de etapas articuladas que produz a solução de um problema; procedimento sequenciado que leva ao cumprimento de uma tarefa.

Mas de todas essas definições, a mais concisa e simples no contexto computacional e lógico é do livro Algoritmos: Teoria e Prática (CORMEN et al., 2012):

um algoritmo é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída. Portanto, um algoritmo é uma sequência de etapas computacionais que transformam a entrada na saída.

Temos diversas visões na definição de algoritmos, seja na visão lógica, computacional ou matemática. Na minha definição, um algoritmo é um conjunto de ações com regras finitas que geram um resultado. Uma entrada e suas definições produzem uma saída.

Design de Algoritmos

Entendemos o conceito base de um algoritmo, mas como podemos construir o algoritmo para chegar na solução do problema ? O princípio fundamental é compreender de qual problema estamos tentando resolver de forma computacional (Devemos lembrar também que nem todo problema é computável, mas isso é debate para outro artigo). Então vemos que isso é um processo. Nada se resolve com tentativa e erro, devemos construir primeiro minuciosamente o design, e depois escrever o programa. E para chegarmos a isso, devemos dividir as etapas em processos simples.

Conhecimento de Domínio

O conhecimento de domínio são os pré-requisitos de resolução de problemas. Devemos conhecer o campo que estamos tentando resolver. Exemplo, existem problemas que demandam de Álgebra, Geometria, Cálculo, Lógica Matemática e outros temas que necessitam de conhecimento prévio para a sua solução.

Linguagem de Programação vs Algoritmos

Algoritmos você escrever de qualquer forma, seu idioma materno, uma definição pessoal, não existe restrição. A única regra é que seja de fácil entendimento para você e para outra pessoa que esteja lendo o algoritmo. Logo o seu destino é o design da implementação. Enquanto para criarmos programas, utilizamos linguagens de programação. Logo, no algoritmo analisamos, enquanto nos programas implementamos e testamos.

Análise Prioritária e Testes posteriores

Quando estamos analisando algoritmos e programas, temos objetivos parecidos, no entanto os métodos e dependências são distintos. Análise Prioritária é tudo relacionado a construção do design de um algoritmo, na análise, as linguagens são independentes, ou seja, não temas restrição de idioma ou linguagem de programação. São também hardware independentes, pois podemos escrever algoritmos em papel e caneta, em quadro branco, em um quadro digital. Na análise de performance, observamos as funções de tempo e espaço(detalharemos em seguida).

Nos testes posteriores, é tudo relacionado a sua implementação, logo temos linguagens dependentes, estruturas únicas e exclusivas, são dependentes de hardware. Em performance de programas no contexto geral analisamos o tempo de execução e os bytes(1 byte é igual a 8 bits) de memória utilizados.

Características de Algoritmos

Todo algoritmo tem uma estrutura, adicionamos entradas, e esperamos alguma saída. Na definição formal:

  • Um algoritmo deve ter apenas um input ou mais;
  • Um algoritmo deve ter no mínimo um output;
  • Na definição, cada declaração em um algoritmo, possui um significado. E todo problema dever ser entendido, ou não poderá ser resolvido;
  • Algoritmos são finitos, eles tem sempre um estrutura de parada. Definimos um conjunto de dados finitos e declarados;
  • Eles devem ser efetivos, ou seja, cada declaração deve fazer sentido para o domínio do problema. Nada é mágico, tudo tem uma estrutura determinada.

Como escrever e analisar um algoritmo ?

Existem várias formas de descrever algoritmos, mas sempre depende do modelo de linguagem utilizada. O que deve ser clara, e não criar estruturas complexas que dificultam a legibilidade do algoritmo.

1: Algorithm swap(a, b)
2:	Begin
3:		temp := a;
4:		a := b;
5:		b := temp;
6:	End

Veja esse exemplo, nesse algoritmo, definimos um modelo de linguagem para sua representação.

  • Algorithm para a declaração nomeada de um algoritmo;
  • Begin para indicar que o algoritmo iniciou um bloco de execução;
  • End para indicar que o algoritmo finalizou o bloco de execução;
  • a declaração := para indica a assinatura de uma variável;

Quando vamos analisar algoritmos, temos algumas métricas que podemos nos basear. E informações que também os algoritmos podem nos entregar. No geral, sempre depende do contexto, e o domínio do problema que estamos tentando resolver.

  • Tempo: Analisar a complexidade de tempo do algoritmo;
  • Espaço: Analisar a complexidade de espaço do algoritmo;
  • Transferência de dados pela rede;
  • Quanto de energia está sendo consumida ?
  • Quantos registradores de CPU estão sendo consumidos ?

Método de Contagem de frequência

Esse método é baseado em quantas vezes cada parte do algoritmo é executada, dependendo do tamanho da entrada. Abrindo um parênteses aqui, vamos fazer uma tangente com a notação Big O. Mas não vai ser a finalidade do artigo nesse momento, devo trazer esse conteúdo em futuro próximo.

1. Olhe os comandos um por um

Vamos voltar ao primeiro pseudocódigo que apresentamos, e analisar quantas vezes cada parte do programa é executada. Cada linha/instrução pode ser executada uma única vez ou várias vezes.

Caso 1

1: Algorithm swap(a, b)
2: 	Begin
3:		temp := a; (1)
4:		a := b; (1)
5:		b := temp; (1)
6:	End
  1. Na linha 1, definimos o algoritmo swap, com suas duas variáveis como argumento.
  2. Na linha 2, definimos o bloco de início de execução do algoritmo.
  3. Na linha 3, criamos a variável temp, e assinamos o valor de a em temp, aqui declaramos que a ação foi realizada uma vez.
  4. Na linha 4, assinamos o valor de b ao valor de a, aqui a contagem de frequência de execução também é igual a 1.
  5. Na linha 5, assinamos o valor temp a variável b que está com a cópia original do valor de a. A contagem de frequência é igual a 1.
  6. Por fim, na linha 6, finalizamos a execução do algoritmo.

Na análise de tempo desse algoritmo, temos a resolução de f(n) = 3, que é o resultado do somatório dos tempos de cada unidade de tempo.

Na análise de espaço, cada variável declarada, ocupa o espaço de 1, logo _S(n) = 3 word_. Na análise em notação Big O, dizemos que esse programa é de origem constante, logo O(n) = 1.

Análise de caso 2

1: int x = 0;        // executa 1 vez
2: for (int i = 0; i < n; i++)  // executa n vezes
3:     x = x + 1;    // também n vezes (porque está dentro do for)

Aqui, a linha 1 é constante (1 vez), a linha 3 é executada n vezes → Complexidade: O(n)

2. Quando é n², n³, etc.?

Geralmente isso acontece quando temos laços aninhados (um dentro do outro):

for (int i = 0; i < n; i++) { // n
    for (int j = 0; j < n; j++) { // n
        x = x + 1;
    }
}
  • O laço de fora repete n vezes
  • O laço de dentro repete n vezes PARA CADA repetição do laço de fora Total de execuções: n × n = n² → Complexidade: O(n²)

Se tiver três for aninhados, será n³, e por aí vai.

3. Quando é n + 1, 2n, etc.?

  • Se tiver uma parte que executa 1 vez, e uma parte que executa n vezes:
print("Início");  // 1 vez
for (int i = 0; i < n; i++) {
    print(i);     // n vezes
}

Total: 1 + n → Complexidade: O(n) (não usamos o +1 porque, para grandes valores, o n domina)

Tangente com Notação Big-o

Sempre usamos o termo que mais cresce com o valor de n.

Expressão TotalComplexidade (Big-O)
1 + nO(n)
5n + 20O(n)
2n² + 3n + 7O(n²)
100n³ + 50n² + 2O(n³)

O que sempre importa é o termo dominante.

Na notação Big-O, medimos como o algoritmo cresce exponencialmente pelo tempo e espaço. Cada implementação tem um algoritmo melhor, pior e casos esperados. Mas isso dependente do contexto da implementação.

Porque precisamos do Big-O ?

Ele nos ajuda a escrever melhores programas, alinhando o melhor da estrutura de dados para encontrar o melhor e mais eficiente código.

Sobre velocidade e memória

Tem uma correlação entre o espaço e tempo. Sempre perdemos algo quando priorizamos um a outro.

  1. Se você quer ser rápido, você tem que usar mais memória.
  2. Se você quer usar menos memória, você tem que ser mais lento.

Conclusão

A construção do design de algoritmos é imprescindível para criarmos códigos e programas melhores. Quando começamos a trabalhar com sistemas de milhões de usuários, ou que de certa forma nosso código impacta diretamente a performance da execução do sistema, devemos olhar primeiro na fonte, nossos algoritmos e estruturas de dados.

Referências

Discuss on X • View on GitHub