(1) Dado um problema, como encontramos um algoritmo eficiente para sua solução?
(2) Encontrado um algoritmo, como comparar este algoritmo com outros algoritmos que solucionam o mesmo problema?
(3) Como deveríamos julgar a qualidade de um algoritmo?
(4) Qual é o algoritmo de menor custo possível para resolver um problema particular?
Questões desta natureza são de interesse para programadores e cientistas da computação. Algoritmos podem ser avaliados por uma variedade de critérios. Na maioria das vezes estamos interessados na taxa de crescimento do tempo ou de espaço necessário para a solução de grandes problemas.
Uma maneira de comparar algortimos é por meio da notação O. Abaixo temos uma tabela com os comportamentos mais comuns relacionados ao tempo para execução de um algoritimo.
Tabela 1- Comportamentos comuns em consumo de tempo
| Função | Significado ( tamanho da entrada = n) |
| 1 | tempo constante – o número de operações é o mesmo para qualquer tamanho da entrada |
| n | tempo linear – se n dobra, o número de operações também dobra |
| n2 | tempo quadrático – se n dobra, o número de operações quadruplica |
| log n | tempo logarítmico – se n dobra, o número de operações aumenta de uma constante |
| nlog n | tempo n log n - se n dobra, o número de operações ultrapassa o dobro do tempo da entrada de tamanho n |
| 2n | tempo exponencial - se n dobra, o número de operações é elevado ao quadrado |
Algumas expressões de O são tão freqüentes que receberam denominações próprias:
Tabela 2- Algumas expressões de O
| Expressão | Nome |
| O(1) | Constante |
| O(log n) | Logarítmica |
| O(log2n) | Log quadrado |
| O(n) | Linear |
| O(nlog n) | n log n |
| O(n2) | Quadrática |
| O(n3) | Cúbica |
| O(2n) | Exponencial |
A Figura 1 mostra esse comportamento de maneira gráfica.
Figura 1 - Represetação gráfica da Tabela 1
No comments:
Post a Comment