-
Introdução à Análise de Algoritmos
A análise de desempenho é uma etapa fundamental na concepção de um algoritmo. Embora aspectos como legibilidade, simplicidade e modularidade de uma solução sejam importantes para a sua manutenabilidade, o desempenho de uma solução é muito relevante para a sua adoção.
Leia mais… -
Análise Assintótica
No material introdutório de análise de algoritmos aprendemos a definir a função que descreve o custo de execução de algoritmos. Vimos exemplos simples cujas funções são também simples. Contudo, vamos supor que a função que descreve o tempo de execução de um algoritmo é dada por:
Leia mais… -
Análise de Algoritmos Recursivos
Até aqui vimos como analisar algoritmos iterativos, lembra? Esse processo pode ser resumido pelos seguintes passos: identificar operações primitivas; identificar a quantidade de vezes que cada uma dessas primitivas é executada; Somar essas execuções.
Leia mais… -
Ordenação por Comparação: Selection Sort
Direto ao ponto Se você pedir para alguém que não é familiarizado com algoritmos para que ordene uma sequência de números, há uma probabilidade alta dessa pessoa aplicar o Selection Sort.
Leia mais… -
Ordenação por Comparação: Insertion Sort
Direto ao ponto O Insertion Sort tem como rotina base a inserção ordenada. A ideia é executar várias vezes essa rotina para ordenar um array. Para ser exato, se executarmos $N - 1$ vezes a rotina de inserção ordenada em um array o resultado é a ordenação completa do mesmo.
Leia mais… -
Ordenação por Comparação: Merge Sort
Merge Sort é um algoritmo eficiente de ordenação por divisão e conquista. Se nossa missão é ordenar um array comparando seus elementos, do ponto de vista assintótico, $n * \log n$ é o nosso limite inferior.
Leia mais… -
Ordenação por Comparação: Quick Sort
Quick Sort é um algoritmo eficiente de ordenação por divisão e conquista. Apesar de ser da mesma classe de complexidade do Merge Sort e do Heap Sort, o Quick Sort é na prática o mais veloz deles, pois suas constantes são menores.
Leia mais… -
Ordenação Linear: Counting sort
Os algoritmos de ordenação que vimos até então utilizam comparação para estabelecer a ordem entre os elementos de uma sequência. Primeiro vimos três algoritmos $\Theta(n^2)$: Selection Sort, Insertion Sort e Bubble Sort.
Leia mais… -
Listas Baseadas em Arrays (ArrayList)
Array é a primeira estrutura de dados que abordamos na disciplina. Há razões para essa escolha. Em primeiro lugar, arrays estão presentes na biblioteca padrão de grande parte das linguagens de programação.
Leia mais… -
Listas Ligadas (LinkedList)
Problemas No material sobre ArrayLists discutimos algumas preocupações oriundas do uso de arrays e que estão todas conceitualmente relacionadas ao fato de que o array é uma estrutura de tamanho fixo.
Leia mais… -
Tabelas Hash
Quando tratamos de estrutura de dados estamos sempre interessados na eficiência de operações fundamentais de coleções, como busca, inserção e remoção. Nesse sentido, o array, embora seja uma estrutura elementar, é um excelente escolha para diversos cenários, pois nos fornece acesso, inserção e remoção em tempo $O(1)$.
Leia mais… -
Uma aula só com perguntas: Endereçamento Aberto
Neste artigo vou descrever um experimento que fiz em sala de aula. Tentei lecionar Resolução de Colisões em Tabelas Hash utilizando apenas perguntas para a turma. Eu estou no meu segundo ano como professor da UFCG e já me cansei de usar slides em sala de aula.
Leia mais… -
Árvores Binárias de Pesquisa
Definições e Propriedades Árvores binárias são estruturas de dados fundamentais no contexto de Ciência da Computação. Em particular, Árvores Binárias de Pesquisa são aplicadas na solução de diversos problemas que demandam eficiência em operações básicas, como busca.
Leia mais… -
Heap
Nem toda fila segue a política de acesso First In First Out (FIFO). Na verdade, em vários cenários do dia a dia, as filas que entramos possuem uma política diferente: são filas de prioridade.
Leia mais…