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.
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:
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.
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.
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.
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.
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.
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.
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.
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.
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)$.
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.
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.
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.