Please enable JavaScript.
Coggle requires JavaScript to display documents.
Eficiência de Algoritmos - Coggle Diagram
Eficiência de Algoritmos
Foco: tempo de execução e memória
Análise da Framework
O
tamanho
do input importa, entradas maiores demandam mais tempo de execução. No entanto, a definição desse parâmetro pode variar dependendo do problema.
Em
relação ao tempo
, não é possível fazer essa medida de acordo com os segundos pois esse tempo vai variar de máquina para máquina.
Logo, observamos a operação básica, aquela que leva mais tempo dentro do algoritmo e geralmente é a principal. Conta-se o número de vezes que ela é realizada
A fórmula é: T (n) ≈ copC(n).
obs: deve ser usada com cuidado, pois só contém infos da operação básica.
A
ordem de crescimento
é essencial para diferenciar algoritmos eficientes e ineficientes.
Algoritmos logarítmicos crescem mais lentamente, enquanto exponenciais crescem rapidamente, mas o fatorial é o que tem mais crescimento.
Eficiência por casos:
Melhor Caso:Executa o menor número de operações possíveis.
Médio Caso:obter suposições probabilísticas sobre a distribuição dessas entradas. É essencial porque, para muitos algoritmos importantes, a eficiência de caso médio é muito melhor do que o que o pior caso pessimista sugere.
Pior Caso: Executa o maior número de operações básicas. Mais crucial pois oferece limite superior garantido ao algoritmo.
Introdução Informal às Notações Assintóticas
objetivo das notações assintóticas é classificar a função de tempo de execução de um algoritmo. Geralmente com C(n), comparando-a com uma função mais simples g(n)
Big O (Limite superior): Pior caso.
O(g(n)) é o conjunto de todas as funções que têm uma ordem de crescimento menor ou igual a g(n).
Big Omega Ω (Limite inferior): Melhor caso.
Ω(g(n)) é o conjunto de todas as funções que têm uma ordem de crescimento maior ou igual a g(n)
Big Theta Θ (Crescimento exato): Θ(g(n)) é o conjunto de todas as funções que têm a mesma ordem de crescimento que g(n)
algoritmos de uma classe assintótica melhor tendem a superar os de uma classe pior, especialmente quando se compara um algoritmo polinomial com um exponencial ou pior. A ordem de crescimento é, portanto, o principal indicador de eficiência.
analisar a eficiência de tempo de algoritmos não recursivos
O que fazer:
Decidir parâmetro de tamanho de input (n)
Identificar operação básica
Verificar se a entrada depende de outras propriedades
Montar uma soma que expresse o número de vezes que a operação básica é executada
Calcular soma
analisar a eficiência de tempo de algoritmos recursivos
O que fazer:
Decidir parâmetro de tamanho de input (n)
Identificar operação básica
Verificar se a entrada depende de outras propriedades
Montar uma relação de recorrência (M(n) em função de M(tamanho menor)) com uma condição inicial apropriada.
Resolver a recorrência (encontrar uma fórmula explícita) ou, pelo menos, determinar a ordem de crescimento da solução.
Análise de algoritmos
Análise empírica:
Resultados dependem da amostra de entrada e do computador usado.
O que fazer:
Entender o propósito do experimento: Definir o objetivo
Decidir a métrica (M) e a unidade de medida: Escolher entre contar a operação básica ou medir o tempo físico
Decidir as características da amostra de entrada
Preparar o programa
Gerar a amostra de entradas
Executar o Algoritmo e registrar os dados
Analisar os Dados
Escolha da métrica de eficiência: existem duas opções.
Inserir um contador no programa (geralmente no loop mais interno) para registrar o número de vezes que a operação básica é executada.
-Usar comandos de sistema ou funções da linguagem para medir o tempo de execução
Sobre a definição da entrada: Pense no crescimento dessas amostras e o seu tamanho.