semnomeComplexidade

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ário verificar 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 quantidade de 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 mais utilizada.

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 modelo matemá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 de complexidade:
• 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 pelo nú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 de espaç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