DAA - Análise de Algoritmos
Na análise teórica de algoritmos, é comum estimar sua complexidade no sentido assintótico, ou seja, estimar a função de complexidade para uma entrada arbitrariamente grande. O termo"analysis of algorithms" foi cunhado por Donald Knuth.
A análise de algoritmos é uma parte importante da teoria da complexidade computacional, que fornece estimativa teórica para os recursos necessários de um algoritmo para resolver um problema computacional específico. A maioria dos algoritmos é projetada para funcionar com entradas de comprimento arbitrário. A análise de algoritmos é a determinação da quantidade de recursos de tempo e espaço necessários para executá-lo.
Normalmente, a eficiência ou o tempo de execução de um algoritmo é estabelecido como uma função relacionando o comprimento de entrada ao número de etapas, conhecido como time complexity, ou volume de memória, conhecido como space complexity.
A necessidade de análise
Neste capítulo, discutiremos a necessidade de análise de algoritmos e como escolher um algoritmo melhor para um problema específico, visto que um problema computacional pode ser resolvido por algoritmos diferentes.
Ao considerar um algoritmo para um problema específico, podemos começar a desenvolver o reconhecimento de padrões de forma que tipos semelhantes de problemas possam ser resolvidos com a ajuda desse algoritmo.
Os algoritmos são frequentemente bastante diferentes uns dos outros, embora o objetivo desses algoritmos seja o mesmo. Por exemplo, sabemos que um conjunto de números pode ser classificado usando diferentes algoritmos. O número de comparações realizadas por um algoritmo pode variar com outros para a mesma entrada. Conseqüentemente, a complexidade de tempo desses algoritmos pode ser diferente. Ao mesmo tempo, precisamos calcular o espaço de memória necessário para cada algoritmo.
A análise do algoritmo é o processo de analisar a capacidade de resolução de problemas do algoritmo em termos de tempo e tamanho necessários (o tamanho da memória para armazenamento durante a implementação). No entanto, a principal preocupação da análise de algoritmos é o tempo ou desempenho necessários. Geralmente, realizamos os seguintes tipos de análise -
Worst-case - O número máximo de etapas realizadas em qualquer instância de tamanho a.
Best-case - O número mínimo de etapas realizadas em qualquer instância de tamanho a.
Average case - Um número médio de etapas realizadas em qualquer instância de tamanho a.
Amortized - Uma sequência de operações aplicadas à entrada de tamanho a média ao longo do tempo.
Para resolver um problema, precisamos considerar o tempo e também a complexidade do espaço, pois o programa pode ser executado em um sistema onde a memória é limitada, mas o espaço adequado está disponível ou pode ser vice-versa. Neste contexto, se compararmosbubble sort e merge sort. A classificação por bolha não requer memória adicional, mas a classificação por mesclagem requer espaço adicional. Embora a complexidade de tempo da classificação por bolha seja maior em comparação com a classificação por mesclagem, podemos precisar aplicar a classificação por bolha se o programa precisar ser executado em um ambiente onde a memória é muito limitada.