Please enable JavaScript.
Coggle requires JavaScript to display documents.
Análise de Algoritmos - Coggle Diagram
Análise de Algoritmos
Paradigmas de Criação de Algoritmos
Divisão e Conquista
Programação Dinâmica
Gula
Busca Local
Aproximação
correção e desempenho dos algoritmos
Correção
Quando um algoritmo resolve um problema?
ao receber a descrição de qualquer instância (valores atribuídos aos parâmetros do problema, conjunto de dados particular do problema) do problema (coleção de “casos particulares” chamados instâncias)
Devolve uma solução da instância
Ou...informa que a instância não tem solução
Desempenho
Quanto tempo o algoritmo consome para processar uma entrada de tamanho n?
▶Suponha que A é um algoritmo para um certo problema
▶Seja t(I) a quantidade de tempo que A consome para processar uma instância I do problema
▶Queremos estudar o comportamento de tempo em função do tamanho das instâncias
▶Para cada n,sejam T1(n) e T2(n) o mínimo e o máximo, respectivamente, de t(I) para todas as instâncias I que têm tamanho n
▶Portanto, T1(n) ≤ t(I) ≤ T2(n) para toda instância I de tamanho n
▶Dizemos que as
funções
T1 e T2 medem o consumo de tempo do algoritmo A no melhor caso e no pior caso, respectivamente
Consumo de tempo?
proporcional ao número de operações elementares que o algoritmo executa ao processar a instância
Operações elementares
▶Uma operação aritmética entre variáveis do algoritmo
▶Uma comparação entre duas variáveis
▶Uma atribuição de valor a uma variável
escolher uma operação específica de modo o consumo de tempo do algoritmo seja proporcional ao número de execuções dessa operação
Notação assintótica
(eliminar a dependência da máquina) (Ο, Ω, Θ)
Concentra-se no valores grandes para n
Exemplos
Complexidade Computacional
caracterização matemática para avaliar o desempenho do algoritmo
Exemplo Fibonacci(n)