Complexidade de algoritmos

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1076 palavras )
  • Download(s) : 0
  • Publicado : 26 de maio de 2012
Ler documento completo
Amostra do texto
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 umataxa 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 assumiro 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 quevai 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 talmuitos testes. No entanto é muito usado pois é também o que representa mais correctamente a complexidade do algoritmo.
Upper Bound
Seja dado um problema, por exemplo, multiplicação de duas matrizes quadradas de ordem n (n*n). Conhecemos um algoritmo para resolver este problema(pelo método trivial) de complexidade O(n3). Sabemos assim que a complexidade deste problema não deve superar O(n3), umavez que existe um algoritmo desta complexidade que o resolve. Um limite superior (upper bound) deste problema é O(n3). O limite superior de um algoritmo pode mudar se alguém descobrir um algoritmo melhor. Isso de facto aconteceu com o algoritmo de Strassen que é de O(nlog 7). Assim o limite superior do problema de multiplicação de matrizes passou a ser O(nlog 7). Outros pesquisadores melhoraramainda este resultado. Atualmente o melhor resultado é o de Coppersmith e Winograd de O(n2.376).
O limite superior de um algoritmo é parecido com o recorde mundial de uma modalidade de atletismo. Ela é estabelecida pelo melhor atleta (algoritmo) do momento. Assim como o recorde mundial o limite superior pode ser melhorado por um algoritmo ( atleta ) mais veloz.
Lower Bound´
Às vezes é possiveldemonstrar que para um dado problema, qualquer que seja o algorimo a ser usado o problema requer pelo menos um certo número de operações. Essa complexidade é chamada Limite inferior ( Lower Bound ). Veja que o limite inferior dependo do problema mas não do particular algoritmo. Usamos a letra Ω em lugar de O para denotar um limite inferior.
Para o problema de multiplicação de matrizes de ordem n,apenas para ler os elementos das duas matrizes de entrada leva O(n2). Assim uma cota inferior trivial é Ω(n2).
Na analogia anterior, um limite inferior de uma modalidade de atletismo não dependeria mais do atleta. Seria algum tempo minimo que a modalidade exige, qualquer que seja o atleta. Um limite inferior trivial para os 100 metros seria o tempo que a velocidade da luz leva a percorrer 100...
tracking img