Complexidade Computacional

Olá Pessoal,

Como eu tenho uma prova sobre complexidade computacional, o post de hoje será sobre isso.
Servirá, no meu caso, para rever o conteúdo, espero que de alguma forma possa ajudá-los também.  

O material utilizado para a elaboração deste post é de anotações em sala de aula, pesquisas (segue ao final do post alguns links) e livros (também ao final do post contém os dados).

Como sabemos, o algoritmo nada mais é do que uma sequência de passos a serem executados que resolverão um problema. Os exemplo mais clássicos disso são, a receita de bolo e a troca da lâmpada, lembram?

A complexidade do algoritmo está relacionada ao trabalho que ele terá na execução. Por exemplo, quanto aumenta o custo, proporcionalmente ao número de dados?

Como fazer a escolha do algoritmo de acordo com a complexidade computacional?

• Do ponto de vista de DESEMPENHO
• SORT é melhor
• BOOLEAN é pior
• Neste caso, melhor é considerado o que exige menos trabalho.

A complexidade é medida de acordo com a quantidade de dados de entrada (n). Vejamos algumas escalas.

• Melhor: quando são necessárias poucas execuções.
• Médio: quando há a necessidade de probabilidade estatística
• Pior: quando são necessárias muitas execuções.

Complexidade Espacial e Temporal

A complexidade espacial de um algoritmo é o espaço de memória necessário para que ele seja executado até o final. Ou seja, S(n), em que S é o espaço de memória exigido e n o tamanho da entrada.

Já a complexidade temporal é o tempo de execução, ou seja, o tempo que um algoritmo demora para ser executado. Ele pode ser representado por T(n), sendo que T é o tempo de execução em função do tamanho da entrada, representado por n.

Notação de O grande

Na prática, é difícil (senão impossível) prever com rigor o tempo de execução de um algoritmo ou programa. 

• Para obter o tempo é necessário pelo menos: constantes multiplicativas (normalmente estas constantes são tempos de execução de operações atômicas) e parcelas menos significativas  para  os valores grandes de n.
• Identificam-se  as operações dominantes (mais frequentes ou mais demoradas) e determina-se o número de vezes que são executadas (e não o tempo de cada execução, que seria uma constante multiplicativa).

Maiores detalhes da análise assintótica, podem ser acessadas neste link: Ordem de O.

Classes de Complexidade

Conforme visto anteriormente, a complexidade computacional é um ramo da matemática computacional que estuda a eficiência dos algoritmos. 

Para medir esta eficiência, frequentemente utilizamos um tempo teórico que o programa leva para encontrar uma resposta em função dos dados de entrada.

Se a dependência do tempo com relação aos dados da entrada for polinomial, o programa é considerado rápido, pois dado um polinômio p(x) sabemos que |p(x)| cresce para +∞ que |x|. cresce Porém, se a dependência do tempo for exponencial, o programa/algoritmo é considerado lento.

• Complexidade constante: O(1) - Independente do número de entradas tem um número fixo de execuções.
• Complexidade logarítmica: O(n) - A operação é realizada para cada elemento de entrada. Exemplo: Lista.
• Complexidade linear: (n) - Ocorre em algoritmos que o problema é dividido em problemas menores. Exemplo: Árvore, Algoritmo de busca binária.
• Complexidade nLogN: O(nLogn) - Mesmo que o anterior, (ocorre em algoritmos em que o problema é dividido em problemas menores), mas que junta as soluções dos problemas menores para compor outras soluções. Exemplo: Algoritmos de execução externa, como vetores auxiliares, MergeSort.
• Complexidade Quadrática: O(n²) - Processado aos pares.
• Complexidade Cúbica: O(n³) - Mesmo que o anterior (processado aos pares), mas com três laços de repetições.
• Complexidade Exponencial: O(n²) - Este é o pior de todos. Geralmente não são úteis do ponto de vista prático porque envolve muita complexidade. Exemplo: tentar descobrir uma senha na "força bruta", ou seja, combinação de todos os caracteres.

Existem várias classes de complexidade, as mais importantes são P e NP.

A classe de algoritmos P é formada pelos procedimentos para os quais existe um polinômio p(n) que limita o número de passos do processamento se este for iniciado com uma entrada n.

A classe de algoritmos NP é aquela para as quais podemos verificar, em tempo polinomial, se uma solução possível é correta.

Os problemas de P estão contidos nos de classe NP. Se um algoritmo pode ser executado em tempo polinomial e tivermos em mãos um possível candidato S à solução, é possível executar o programa, obter uma solução correta C e comparar com com S, para certificar que S é de fato uma solução, tudo em tempo polinomial. 

Fontes utilizadas para compor este post:

http://www-usr.inf.ufsm.br/~andrezc/ia/complexidade.pdf
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/NPcompleto2.html

O livro:

Projeto de algoritmos: Fundamentos, análise e exemplos da internet

 Por Michael T. Goodrich,Roberto Tamassia