Complexidade computacional

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.. 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.

Tipos

• Espacial: Este tipo de complexidade representa o espaço de memória usado para executar o algoritmo, por exemplo.
• Temporal: Este tipo de complexidade é o mais usado podendo dividir-se em dois grupos:
• Tempo (real) necessário à execução do algoritmo.
• Número de instruções necessárias à execução...

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.

• 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.

• 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.

Wikipédia 1, 2