Please enable JavaScript.
Coggle requires JavaScript to display documents.
Analise da eficiencia de um algoritmo - Coggle Diagram
Analise da eficiencia de um algoritmo
duas principais dimensões
Time Efficiency
Space Efficiency
analise do framework
medir o temanho da entrada, geralmente chamamos de n
a unidade de tempo é contada a partir de uma formula: T(n) = Cop * C(n)
onde C(n) é a quantidade de operações feitas no algoritmo e Cop o tempo que ela demora
ordem de crescimento, um algoritmo com complexidade logaritmica cresce mais devagar que um com velocidade exponencial, logo em casos muitos grandes deve-se preferir o logaritmico
best, worst e average case. Best é o caso mais rapido, worst o mais lento e average é o comum
Notações Assintóticas e Classes Básicas de Eficiência
Big Oh (O)
É o conjunto de todas as funções que têm uma ordem de crescimento menor ou igual à de g(n) (dentro de uma constante multiplicativa). Por exemplo,
100n + 5 tem uma ordem de crescimento menor que n², então 100n + 5 ∈ O(n²)
Big omega (Ω)
É o conjunto de todas as funções com uma ordem de crescimento maior ou igual à de g(n). Por exemplo,
n³ tem uma ordem de crescimento maior que n², então n³ ∈ Ω(n²).
Big Theta (Θ)
É o conjunto de todas as funções que têm a mesma ordem de crescimento que g(n). Por exemplo, qualquer função quadrática
an² + bn + c (com a > 0) está em Θ(n²)
analise matematica de algoritmos não recursivos
decidir sobre o parâmetro de tamanho da entrada: Geralmente n
Identificar a operação básica do algoritmo
Verificar a dependência da operação básica
Configurar uma soma: Escrever uma soma que expresse o número total de vezes que a operação básica é executada.
Simplificar a soma
analise matematica de algoritmos recursivos
Decidir sobre o parâmetro de tamanho da entrada (ex: n).
Identificar a operação básica do algoritmo
Verificar a dependência da operação básica: Checar se o número de execuções varia para diferentes entradas do mesmo tamanho. Se variar, analisar o pior caso, caso médio e melhor caso separadamente.
Configurar uma relação de recorrência: Estabelecer uma recorrência, com uma condição inicial apropriada, para o número de vezes que a operação básica é executada.
Resolver a recorrência
Analise empirica dos algoritmos
alternativa a analise matematica
Entender o propósito do experimento
Decidir a métrica de eficiência e a unidade de medida
Decidir as características da amostra de entrada
Preparar um programa que implementa o algoritmo
Gerar uma amostra de entradas
Executar o algoritmo na amostra e registrar os dados
Analisar os dados obtidos
vizualização do algoritmo
Visualização Estática de Algoritmos
Mostra o progresso de um algoritmo através de uma série de imagens paradas
Visualização Dinâmica de Algoritmos
Também chamada de animação de algoritmos, mostra uma apresentação contínua, como um filme, das operações de um algoritmo
aplicaçoes
Pesquisa
Educação