semnomeComplexidade

Páginas: 4 (963 palavras) Publicado: 19 de julho de 2015
Complexidade computacional e
assintótica
• Desenvolvida por dois informáticos estadunidenses, tem
a finalidade de comparar a eficiência dos algoritmos ,
mostrando o custo que ele terá.
• É necessárioverificar essa eficiência, pois caso contrário,
um algoritmo pode se tornar inútil (a grande quantidade
de entrada de dados gera um tempo de execução
inviável).

Complexidade: medida da quantidadede
recursos consumidos durante a execução do
programa.
A teoria qualitativamente classifica os problemas
baseando-se nas medidas de complexidade.
É analisada por tempo ou espaço, sendo a
primeira maisutilizada.

Teoria da complexidade de
Algoritmo
Classifica um algoritmo de acordo com seu custo.
Pode:
• Comparar algoritmos;
• Determinar se um algoritmo é ótimo;
Medida de efeciência assintótica:usada quando se
desprezam certos tempos de uma função ou
quando calcular uma função é difícil ou
impossível.

Ordem de Grandeza (O)
A complexidade de um algoritmo é analisada segundo um modelomatemático
analítico: supõe-se que o algoritmo vai trabalhar sob uma entrada de dados
tamanho n, ou seja: existem n informações distintas a serem tratadas. A
análise considera os seguintes fatores decomplexidade:
• Tempo de Execução: analisa-se o custo de cada operação realizada em
função do tamanho da entrada (n). Por exemplo: algoritmos de ordenação
têm a sua complexidade de tempo determinada pelonúmero de comparações
realizadas em função de n.
• Espaço em Memória: espaço necessitado pelo algoritmo para sua execução.
Em geral, quanto menor a complexidade de tempo, maior a sua complexidade
deespaço: maior agilidade no processo implica mais uso de memória.

A complexidade de um algoritmo é uma “ordem de grandeza”, medida de
acordo com o crescimento de uma função. Como notação, usamos a letra‘O’.
A análise é feita observando-se os fatores abaixo:
• Limite superior: representa a complexidade em si e é analisado usando-se
uma entrada suficientemente grande de dados. A ordem abaixo, por...
Ler documento completo

Por favor, assinar para o acesso.

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!