Complexidade computacional: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 61:
: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).
* [[Complexidade Caso médio|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 [[recursividade|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 [[logaritmo|função logarítmica]]. Este procedimento de busca (conhecido como [[busca binária]]) em uma estrutura [[Teoria da ordem|ordenada]] têm complexidade logarítmica
* [[Complexidade Pior caso|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.
| |||