null
US
Sign In
Sign Up for Free
Sign Up
We have detected that Javascript is not enabled in your browser. The dynamic nature of our site means that Javascript must be enabled to function properly. Please read our
terms and conditions
for more information.
Next up
Copy and Edit
You need to log in to complete this action!
Register for Free
6854504
Análise e Complexidade de Algoritmos
Description
Concursos Públicos IFS Mind Map on Análise e Complexidade de Algoritmos, created by Izabella Rezende on 31/10/2016.
No tags specified
ifs
concursos públicos
Mind Map by
Izabella Rezende
, updated more than 1 year ago
More
Less
Created by
Izabella Rezende
almost 8 years ago
20
1
0
Resource summary
Análise e Complexidade de Algoritmos
Procedimentos computacionais
Entradas
Saídas
Algoritmo correto
Resolve o problema
Avaliar eficiência/desempenho
Considerado tecnologia
Tão importante como hardware
Computador infinitamente rápido?
Recursos limitados
Processamento
memória
Ordenação
Inserção
Exemplo do baralho
loop invariante
ao final de cada etapa uma parte da solução
provar a corretude
Inicialização
verdadeira antes da primeira iteração
manutenção
durante a execução
término
Complexidade de Algoritmos
Tempo
Depende da entrada
Qtd de itens
custo linear
melhor caso
melhor caminho
já ordenado
loop
custo quadrático
maior tempo de execução
executar todos os passos
pior caso
custo constante
instruções simples
Um algoritmo é melhor se o custo de pior caso for menor
Comportamento
Complexidade Assintótica
Comportamento de acordo com o crescimento da entrada
Tende ao infinito
Assintoticamente mais eficiente
um algoritmo que é assintoticamente mais eficiente será a melhor escolha para todas as entradas, exceto as muito pequenas
Medidas de complexidade/Custo
Melhor caso
Menor tempo de execução sobre todas as possíveis entradas de tamanho N
pior caso
maior tempo de execução
caso médio
média dos tempos de todas as as entradas
Descarta termos constantes
Prevê recursos neccessários
Resolver problemas computacionais
Divisão e conquista
Ordenação por intercalação
Divide em 2 pedaços
Classificar recursivamente
Intercalar as 2 metades
Custo: Equação de recorrência
2*T(n/2) --divisão + O(n) -Merge
Recursividade
Chamar a si mesmo
Passos:
Dividir
Conquistar
Combinar
Merge
QuickSort
Estudar n. de vezes que operações são executadas
Algoritmos Gulosos
Busca resolver problemas de otimização
caminho mínimo/menor custo
Técnica de construção de algoritmos
Preocupa-se a melhor opção LOCAL viável
Lembrar PACMAN/Come e não vomita
Algoritmos simples e de fácil implementação
Conjunto de candidatos
Escolhidos
Rejeitados
Passo
Escolhe qual elemento é mais viável
Sequencia de decisões para alcançar o prob.
Ou faz parte da decisão, ou é descartado
Lembrar do problema do troco
Backtracking
Busca exaustiva/completa
Método Sistemático
Estratégia de resolução de problemas
Se der errado, volta e escolhe outro caminho
Medir eficiência
Algoritmos diferentes resolvem o mesmo problema com a mesma eficiência?
Complexidade computacional
Custo = memória + tempo
Análise
Empírica
Na execução
Analisa desempenho
custos não aparentes/alocação a memória
computadores e linguagens
resultado pode ser mascarado pelo hardware
pode existir outra execução no momento
Matemática
Estudo formal
Ideia por trás do algoritmo
Independente de hardware
Ignora detalhes de baixo nível (LP, hardware)
ident. como o algoritmo se comporta c entrada
Media attachments
5a3600d8-5e4c-44bd-b79d-7df3081a00fc.PNG (image/PNG)
Show full summary
Hide full summary
Want to create your own
Mind Maps
for
free
with GoConqr?
Learn more
.
Similar
OBJETIVOS E FINALIDADES DO INSTITUTOS FEDERAIS
ALOAN CABRAL0485
The Rock Cycle
eimearkelly3
Chemistry General Quiz - 2
lauren_johncock
FCE Practice Quiz - B2
miminoma
A2 Organic Chemistry - Reactions
yannycollins
GCSE Physics Revision notes
Megan McDonald
AQA GCSE Physics Unit 3 Mindmap
Gabi Germain
Bay of Pigs Invasion : April 1961
Alina A
7 Elements of Good Design
Micheal Heffernan
SFDC App Builder (76-100)
Connie Woolard
Data Protection Act 1998
Carina Storm
Browse Library