Please enable JavaScript.
Coggle requires JavaScript to display documents.
Análise da Eficiência de Algoritmos, Mathematical Analysis of Nonrecursive…
Análise da Eficiência de Algoritmos
Eficiencia dos algoritmos
Tempo
Tempo de execução
Espaço
Espaço de memória
Input
o input é n, podendo ser o grau de um polinomio, numero de elementos de uma matriz, numero de elementos de uma lista, etc
Cenários
Pior
Executa o numero maximo de operações significantes
Melhor
Melhor input possivel para eficiencia
Médio
Input medio, padrao
n / log n / n log n / n^2 / n!
Mathematical Analysis of Nonrecursive Algorithms
Determinar a eficiencia em funcao da entrada em um algoritmo nao recursivo necessita alguns passos
Identificar a operação principal, normalmente no loop mais interno
Verificar a variacao de acordo com o parametro de entrada
Mathematical Analysis of Recursive Algorithms
Identificar a operação basica
Verificar a variacao de acordo com o parametro de entrada
Estabelecer a recorrencia
Idenficar a ordem de crescimento
Definir o paramentro de entrada, n
Temos como exemplo a torre de hanoi
Empirical Analysis of Algorithms
Nem sempre é possivel fazer a analise perfeita e matematicamente precisa de um algoritmo, por isso é necessario observa-lo na pratica para avaliar sua eficiencia
Primeira é necessario escolher a metrica de analise, podendo ser tempo, memoria, numero de execucoies, etc
Use contadores e outras tecnicas para marcar sua metrica escolhida
Repetir os testes
Analise e conclusao dos dados
Algorithm Visualization
Visualização Estática
Mostra o progresso do algoritmo em imagens fixas
Mais simples
Visualização Dinâmica
Exibe as operações do algoritmo em tempo real
Mais dificil
Asymptotic Notations and Basic Efficiency Classes
Funcoes assintoticas
Big O
Funcao que nao cresce mais que outra
Big Omega
Indica que a funcao cresce, pelo menos, mais rapido que a outra
Big Theta
Indica que duas funcoes crescem igualmente