Análise de algoritmos

Em ciência da computação, a análise de algoritmos tem como função determinar os recursos necessários para executar um dado algoritmo. A maior parte dos algoritmos são pensados para trabalhar com entradas (inputs) de tamanho arbitrário. Em geral, a eficiência ou complexidade de um algoritmo é função do tamanho do problema, do número de passos necessário (complexidade temporal) e da complexidade espacial ou de memória do sistema usado para executar o algoritmo. Esta disciplina faz parte da mais vasta teoria da complexidade computacional, que permite fazer estimativas quanto aos recursos necessários para que um algoritmo resolva um determinado problema computacional.

Assim, o objetivo final não é apenas fazer códigos que funcionem, mas que sejam também eficientes. Para isso, deve-se estudar alguns tipos de problemas que podem ser resolvidos computacionalmente. Em seguida, deve ser visto como a abordagem adotada para resolver pode influenciar, levando a um algoritmo mais ou menos eficiente.

"Ao verificar que um dado programa está muito lento, uma pessoa prática pede uma máquina mais rápida ao seu chefe. Mas o ganho potencial que uma máquina mais rápida pode proporcionar é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas. Para obter um ganho maior, é preciso buscar melhores algoritmos. Um bom algoritmo, mesmo rodando em uma máquina lenta, sempre acaba derrotando (para instâncias grandes do problema) um algoritmo ruim rodando em uma máquina rápida. Sempre."

[[:Ficheiro:|Áudio do texto]][[Ficheiro:|220px|noicon|alt=]]
Problemas para escutar este arquivo? Veja a ajuda.

Ver também

• Algoritmo de Quick sort
• Algoritmo Bubble sort
• Donald Knuth, cientista da computação.

Referências bibliográficas

• S. S. Skiena, The Algorithm Design Manual - ISBN 0387948600

[Esconder]

• v
• d
• e

Tópicos em matemática industrial e aplicada
Matemática computacional

• Lógica computacional
• Projeto e análise de algoritmos
• Teoria da informação
• Teoria de códigos
• Criptografia

Matemática discreta

• Álgebra computacional
• Teoria computacional dos números
• Combinatória
• Teoria dos grafos
• Geometria discreta

Física algébrica

• Álgebra de operadores
• Física de partículas e teoria da representação
• Grupo de renormalização
• Integração funcional
• Teoria-M

Física analítica

• Geometria diferencial
• Análise de Fourier
• Análise harmônica
• Análise funcional
• Teoria dos operadores

Análise

• Teoria da aproximação
• Análise numérica
• Equações diferenciais
• Sistemas dinâmicos
• Teoria de controle
• Cálculo variacional

Teoria das probabilidades

• Distribuições de variáveis aleatórias
• Processo estocástico
• Cálculo estocástico
• Integração funcional

Teoria da decisão

• Estatística
• Pesquisa operacional
• Otimização
• Teoria dos jogos
• Economia matemática
• Matemática financeira

Outras aplicações

• Aplicabilidade da matemática (filosofia)
• Biologia
• Química
• Psicologia
• Sociologia

• Categoria
• Portal de matemática

• Portal das tecnologias de informação