Nesta aula, demos os primeiros passos no estudo dos algoritmos, o conceito fundamental que está no coração da ciência da computação. Um algoritmo é uma sequência finita de instruções bem definidas que resolvem um problema específico. Ao longo do dia, exploramos suas características, formas de representação e como medir sua eficiência através da complexidade.

O que é um Algoritmo?

Podemos comparar um algoritmo a uma receita de bolo: cada passo precisa ser executado na ordem correta para obter o resultado esperado. Na computação, algoritmos são a base de todo software, desde um simples programa de soma até sistemas complexos de inteligência artificial.

Formalmente, um algoritmo deve receber uma entrada (que pode ser vazia) e produzir uma saída desejada. Os passos intermediários transformam os dados de entrada até chegar ao resultado. Essa sequência deve ser executada em um tempo finito e cada instrução deve ser suficientemente básica para ser executada por um computador.

Características de um Algoritmo

  • Entrada: zero ou mais quantidades fornecidas externamente.
  • Saída: pelo menos uma quantidade produzida como resultado.
  • Definitude: cada instrução deve ser clara e sem ambiguidade.
  • Finitude: o algoritmo deve terminar após um número finito de passos.
  • Efetividade: cada passo deve ser executável em tempo finito.

Essas propriedades garantem que um algoritmo seja confiável e possa ser implementado em qualquer linguagem de programação.

Representação de Algoritmos

Existem diversas maneiras de representar um algoritmo, cada uma com suas vantagens:

  1. Descrição narrativa: utiliza linguagem natural. É fácil de entender, mas pode conter ambiguidades.
  2. Fluxograma: emprega símbolos gráficos padronizados. É visual e facilita o entendimento do fluxo de controle.
  3. Pseudocódigo: uma linguagem intermediária entre a natural e a de programação. É muito usado em livros e salas de aula por ser independente de linguagem.

Em nosso curso, focaremos no pseudocódigo, por ser uma ferramenta didática poderosa e facilmente traduzível para linguagens reais.

Por que Analisar a Complexidade?

Dois algoritmos podem resolver o mesmo problema, mas com desempenhos muito diferentes. A análise de complexidade nos permite comparar a eficiência de algoritmos sem precisar implementá-los. A medida principal é o tempo de execução em função do tamanho da entrada, representada pela notação Big O.

Notação Big O

A notação Big O descreve o comportamento assintótico de um algoritmo no pior caso. Algumas classes comuns:

  • O(1) – constante: o tempo não depende do tamanho da entrada. Exemplo: acessar um elemento de um array pelo índice.
  • O(log n) – logarítmica: reduz o problema pela metade a cada passo. Exemplo: busca binária em um vetor ordenado.
  • O(n) – linear: o tempo cresce proporcionalmente ao tamanho da entrada. Exemplo: percorrer uma lista para encontrar um elemento.
  • O(n log n): comum em algoritmos de ordenação eficientes (merge sort, quick sort).
  • O(n²) – quadrática: ocorre quando há laços aninhados percorrendo a entrada. Exemplo: ordenação por bolha (bubble sort).

Quanto menor a ordem de crescimento, mais eficiente é o algoritmo para grandes volumes de dados.

Exemplo: Busca Linear vs Busca Binária

Para ilustrar, considere a busca de um valor em um array de n elementos:

  • Busca linear: compara cada elemento até encontrar o desejado. Complexidade O(n).
  • Busca binária: exige que o array esteja ordenado. A cada iteração descarta metade dos elementos. Complexidade O(log n).

Para n = 1.000.000, a busca linear pode exigir até 1 milhão de comparações, enquanto a binária requer apenas cerca de 20. Isso mostra a importância de escolher o algoritmo adequado.

Algoritmos de Ordenação

Ordenar dados é uma tarefa recorrente em computação. Estudamos alguns algoritmos clássicos:

  • Bubble Sort: percorre a lista múltiplas vezes, trocando elementos adjacentes fora de ordem. Complexidade O(n²).
  • Insertion Sort: constrói a parte ordenada incrementalmente, inserindo cada novo elemento na posição correta. O(n²) no pior caso, mas eficiente para dados quase ordenados.
  • Merge Sort: divide a lista ao meio recursivamente e depois intercala as partes ordenadas. Complexidade O(n log n) no pior caso.

Esses exemplos mostram como a escolha do algoritmo impacta diretamente o desempenho.

FAQ – Perguntas Frequentes

O que diferencia um algoritmo de um programa de computador?

Um algoritmo é uma sequência lógica abstrata; um programa é a implementação concreta desse algoritmo em uma linguagem de programação específica.

Qual é a complexidade de um algoritmo com dois laços aninhados?

Se ambos os laços percorrem uma entrada de tamanho n, a complexidade típica é O(n²).

Por que usamos o pior caso na análise Big O?

Para garantir um limite superior confiável. Assim sabemos que o algoritmo nunca será pior do que essa estimativa.

Algoritmos podem ser representados de outras formas além das citadas?

Sim, existem diagramas de atividade UML, árvores de decisão, linguagens formais, entre outras.

Conclusão

Nesta aula, construímos uma base sólida sobre o que são algoritmos, suas propriedades essenciais e como avaliar sua eficiência. Esses conceitos serão aplicados ao longo de todo o curso de Ciências da Computação. Nos próximos dias, aprofundaremos em estruturas de dados e técnicas de projeto de algoritmos.