Análise de algoritmos: diferenças entre revisões
m Checkwiki + ajustes |
|||
Linha 3: | Linha 3: | ||
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. |
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 |
''"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."'' |
||
{{Ouça| |
{{Ouça| |
||
Linha 10: | Linha 10: | ||
}} |
}} |
||
=={{Ver também}}== |
== {{Ver também}} == |
||
* Algoritmo de [[Quick sort]] |
* Algoritmo de [[Quick sort]] |
||
* Algoritmo [[Bubble sort]] |
* Algoritmo [[Bubble sort]] |
||
Linha 18: | Linha 18: | ||
* S. S. Skiena, [http://books.google.com/books?id=TrXd-gxPhVYC&printsec=frontcover&dq=%22Skiena%22+%22The+Algorithm+Design+Manual%22+&sig=c60b6kTmuL9Xsm0GzZnefwt3Cdo The Algorithm Design Manual] - ISBN 0387948600 |
* S. S. Skiena, [http://books.google.com/books?id=TrXd-gxPhVYC&printsec=frontcover&dq=%22Skiena%22+%22The+Algorithm+Design+Manual%22+&sig=c60b6kTmuL9Xsm0GzZnefwt3Cdo The Algorithm Design Manual] - ISBN 0387948600 |
||
{{Portal3|Tecnologias de informação}} |
|||
⚫ | |||
{{DEFAULTSORT:Analise Algoritmos}} |
|||
⚫ | |||
[[en:Analysis of algorithms]] |
[[en:Analysis of algorithms]] |
Revisão das 14h33min de 21 de janeiro de 2012
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