Complexidade computacional

Origem: Wikipédia, a enciclopédia livre.

Foi proposta a fusão deste artigo com: Complexidade (informática).

A Teoria da complexidade computacional é a parte da teoria da computação que estuda os recursos necessários durante o cálculo para resolver um problema. O termo foi criado pelo Juris Hartmanis e Richard Stearns^[1]. Os recursos comumente estudados são o tempo (número de passos de execução de um algoritmo para resolver um problema) e o espaço (quantidade de memória utilizada para resolver um problema). Pode-se estudar igualmente outros parâmetros, tais como o número de processadores necessários para resolver o problema em paralelo. A teoria da complexidade difere da teoria da computabilidade a qual se ocupa de factibilidade de se solucionar um problema como algoritmos efetivos sem levar em conta os recursos necessários para ele.

Os problemas que têm uma solução com ordem de complexidade linear são os problemas que se resolvem em um tempo que se relaciona linearmente com seu tamanho.

Hoje em dia as máquinas resolvem problemas mediante algoritmos que têm como máximo uma complexidade ou custo computacional polinômico, significa dizer que, a relação entre o tamanho do problema e seu tempo de execução é polinômico. Os problemas com custo fatorial ou combinatório estão agrupados em NP. Estes problemas não têm uma solução prática, significa dizer quer, uma máquina não pede resolver-los em um tempo razoável.

[editar] Visão Geral

A importância da complexidade pode ser observada no exemplo abaixo, que mostra 5 algoritmos A1 a A5 para resolver um mesmo problema, de complexidades diferentes. Supomos que uma operação leva 1 milisegundo para ser efetuada. A taboa seguinte dá o tempo necessário por cada um dos algoritmos.

Tk(n) é a complexidade do algoritmo.

	$A 1$	$A 2$	$A 3$	$A 4$	$A 5$
n \|	$T 1 (n) = n$ \|	$T 2 (n) = n l o g n$ \|	$T 3 (n) = n 2$ \|	$T 4 (n) = n 3$ \|	$T 5 (n) = 2 n$
16	0,016s	0,064s	0,256s	4s	1m4s
32	0,032s	0,16s	1s	33s	46 dias
512	0,512s	9s	4m22s	1 dia 13h	$10137$ séculos

A complexidade do tempo de um problema é o número de passos que se toma para resolver uma instância de um problema, a partir do tamanho da entrada utilizando o algoritmo mais eficiente à disposição. Intuitivamente, caso se tome uma instância com entrada de longitude n que pode resolver-se em n² passos, se diz que esse problema têm uma complexidade em tempo de n². Supostamente, o número exato de passos depende da máquina em que se programa, da linguagem utilizada e de outros fatores. Para não ter que falar do custo exato de um cálculo se utiliza a notacão O. Quando um problema têm custo dado em tempo O(n²) em uma configuração de computador e linguagem, este custo será o mesmo em todos os computadores, de maneira que esta notação generaliza a noção de custo independentemente do equipamento utilizado.

[editar] Perspectivas

São usadas três perspectivas no estudo do caso da complexidade:

Melhor Caso – Representado por Ω( ), consiste em assumir que vai acontecer o melhor. Pouco utilizado e de baixa aplicabilidade.

Exemplo 1: Em uma lista telefônica queremos encontrar um número, assume-se que a complexidade do caso melhor é Ω (1), pois está pressupondo-se o número desejado está no topo da lista.

Exemplo 2: Extrair qualquer elemento de um vetor. A indexação em um vetor ou array, leva o mesmo tempo seja qual for o índice que se queira buscar. Portanto é uma operação de complexidade constante Ω (1).

Caso médio – Representado por θ( ). Este é o caso que é o mais difícil de ser determinado, pois, necessita de análise estatística e em conseqüência de muitos testes, contudo é muito utilizado, pois é o que representa mais corretamente a complexidade do algoritmo.

Exemplo: Procurar uma palavra em um dicionário. Pode-se iniciar a busca de uma palavra na metade do dicionário. Imediatamente se sabe se foi encontrada a palavra ou, no caso contrário, em qual das duas metades deve se repetir o processo (é um processo recursivo) até se chegar ao resultado. Em cada busca (ou sub-busca), o problema (as páginas em que a palavra pode estar) vão se reduzindo à metade, o que corresponde com a função logarítmica. Este procedimento de busca (conhecido como busca binária) em uma estrutura ordenada têm complexidade logarítmica θ (In n).

Pior Caso – Representado normalmente por O( ). Se dissermos que um determinado algoritmo é representado por g(x) e a sua complexidade Caso Pior é n, será representada por g(x) = O(n). Consiste em assumir que o pior dos casos pode acontecer, sendo de grande utilização e também normalmente o mais fácil de ser determinado.

Exemplo 1: Será tomado como exemplo o jogo de azar com 3 copos, deve descobrir-se qual deles possui uma moeda debaixo dele, a complexidade caso pior será O(3) pois no pior dos casos a moeda será encontrada debaixo do terceiro copo, ou seja, será encontrada apenas na terceira tentativa.

Exemplo 2: O processo mais comum para ordenar um conjunto de elementos têm complexidade quadrática. O procedimento consiste em criar uma coleção vazia de elementos. A ela se acrescenta, em ordem, o menor elemento do conjunto original que ainda não tenha sido eleito, o que implica em percorrer completamente o conjunto original (O(n), sendo n o número de elementos do conjunto). Esta percorrida sobre o conjunto original se realiza até que se tenha todos seus elementos na seqüência de resultado. Pode-se ver que há de se fazer n seleções (se ordena todo o conjunto) cada uma com um custo n de execução: o procedimento é de ordem quadrática O(n²). Deve esclarecer se de que há diversos algoritmos de ordenação com melhores resultados.

[editar] Ver Também

[editar] Referências

^ Juris Hartmanis and Richard E. Stearns. On the computational complexity of algorithms. Trans. American Mathematical Society, 117:285--306, Maio 1965.