Complexidade de algoritmos

O que é a Complexidade?
A Complexidade de um algoritmo consiste na quantidade de trabalho necessária para a sua execução, expressa em função das operações fundamentais, as quais variam de acordo com o algoritmo, e em função do volume de dados.
Ou seja feita com vistas a se obter uma estimativa do esforço de computação, não em termos de unidade de tempo propriamente, mais em termos de uma taxa de crescimento do tempo de execução em função do “tamanho do problema”, isso é, do tamanho da entrada.
Medidas de Complexidade. 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.
Para o estudo da complexidade são usados três perspectivas :
• Pior Caso
• Melhor Caso
• Caso Médio
Pior Caso
Este método é normalmente representado por O ( ), por exemplo 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 basicamente em assumir o pior dos casos que podem acontecer, sendo muito usado e sendo normalmente o mais fácil de determinar.
Exemplos:
Se por exemplo existirem cinco baús sendo que apenas um deles tem algo dentro e os outros estão vazios a complexidade caso pior será O(5) pois eu no pior dos casos acerto no baú cheio á quinta tentativa.

Melhor Caso
Representa-se por Ω ( )
Método que consiste em assumir que vai acontecer o melhor. Pouco usado. Tem aplicação em poucos casos.
Exemplos:
Se tivermos uma lista de números e quisermos encontrar algum deles assume-se que a complexidade caso melhor é Ω (1) pois assume-se que o numero estaria logo na cabeça da lista. Caso Médio
Representa-se por θ().
Este método é dos três o mais dificil de determinar pois necessita de análise estatistica e como tal