null
US
Iniciar Sesión
Regístrate Gratis
Registro
Hemos detectado que no tienes habilitado Javascript en tu navegador. La naturaleza dinámica de nuestro sitio requiere que Javascript esté habilitado para un funcionamiento adecuado. Por favor lee nuestros
términos y condiciones
para más información.
Siguiente
Copiar y Editar
¡Debes iniciar sesión para completar esta acción!
Regístrate gratis
6854504
Análise e Complexidade de Algoritmos
Descripción
Concursos Públicos IFS Mapa Mental sobre Análise e Complexidade de Algoritmos, creado por Izabella Rezende el 31/10/2016.
Sin etiquetas
ifs
concursos públicos
Mapa Mental por
Izabella Rezende
, actualizado hace más de 1 año
Más
Menos
Creado por
Izabella Rezende
hace alrededor de 8 años
20
1
0
Resumen del Recurso
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
Recursos multimedia adjuntos
5a3600d8-5e4c-44bd-b79d-7df3081a00fc.PNG (image/PNG)
Mostrar resumen completo
Ocultar resumen completo
¿Quieres crear tus propios
Mapas Mentales
gratis
con GoConqr?
Más información
.
Similar
OBJETIVOS E FINALIDADES DO INSTITUTOS FEDERAIS
ALOAN CABRAL0485
Consejos para Estudiar y Citas
maya velasquez
LA FUNCIÓN DE NUTRICIÓN
M.Encina SF
TEST REPASO BIOQUÍMICA 1º BACH
VICTOR MANUEL VITORIA RUIZ
Test Sobre los ríos de España
Grupo Máquinas
Símbolos y Abreviaciones para tomar apuntes
Diego Santos
Conceptos básicos de Economía
María Eugenia Méndez Piamba
Cómo Aprender Idiomas Usando Fichas
Diego Santos
Aprovechando al Máximo los Tests como Recurso de Estudio
Diego Santos
ANATOMÍA HUMANA s/t...
Ulises Yo
El adjetivo
Silvia Rial Martínez
Explorar la Librería