Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fundamentals of the Analysis of Algorithm Efficiency - Coggle Diagram
Fundamentals of the Analysis of Algorithm Efficiency
2.1 - the analysus framework
eficiência de tempo
mais fácil de ser otimizada
eficiência de espaço
tamanho do input
na maioria dos algoritmos quanto maior mais tempo rodando
receber parâmetros argiliza um pouco
unidades de medida para o tempo
operacão básica
podemos achar a ordem de crescimento do algoritmo
grau maior
menos eficiência
grau menor
mais eficiência
tipos de caso
worst-case
amortized efficience
quando o pior caso é muito ruim podemos dividir em (n) operações para melhorar
best-case
averege-case
assumimos possíveis entradas e calculamos a média
usamos quando não só o tamanho, quanto a ordem dos elementos importa
2.2 - asymptotic notation and basic eficiency classes
big oh
todas as funções com ordem de crescimento menot ou igual a g(n)
big omega
todas as funções com ordem de crescimento maior ou igual
big theta
todas as funções com ordem de crescimento igual a g(n)
c(n)
operação básica
g(n)
função básica para comparação
t(n)
tempo de processamento
obs: podemos usar limites para calcular a ordm de crescimento
2.3 - Mathematical analysis of nonrecursive alrgorithms
1 - parâmetro do input
2 - indentificar a operação básica
3 - conferir o mumero de casos segundo o tamnho e, se for necessário; achar o pior e médio caso
4 - fazer o somatório com o número de operações básicas
5 - usar fórmulas para o somatório ou para ordem de crecimento
2.4 - Mathematical analysis of recursive algorithms
1 - parâmetro do input
2 - identificar a operação básica
3 - ver se o número de operações é variável
4 - criar condições de recursão
5 - resolver a recurção ou achar ordem de crescimento
backward substitution
smootness rule
2.6 - empirical analysis of algorithms
1 - entender o propósito do algoritmo
2 - decidir a métrica e a unidade
3 - decidir caracteísticas do input
4 - fazer o programa implementando o algoritmo para os testes
5 - gerar uma amostra de inputs
6 - testar no programa e armazenar os resultados
7 - analizar os dados obtidos
métodos
3 more items...
escola dos inputs
dos menores para os maiores
é preferível usar um padrão de crecimento
usar variados inputs para a média (implementar um random, por exemplo)
metodos de análise
criar um contador para operações básicas
criar uma implementação com tempo
ex: função clock
2.7 - algorithm visualization
static = imagens
dynamic = animações/vídeos
fins de estudo e educacionais
vizualizar inputs e a velocidade do algoritmo