Trabalho

Anhanguera Rio claro

ATPS - 7ª Série
Análise e Complexidade de Algoritmos

Nome: Adauto Fernandes Rocha
Ra: 1060117743

Rio Claro/SP
2013
A complexidade de um algoritmo reflete o esforço computacional requerido para executá-lo. As principais medidas de esforço são tempo e espaço, relacionados a velocidade e quantidade de memória, respectivamente. O esforço computacional não pode ser descrito simplesmente por um número, porque a quantidade de trabalho requerido em geral depende da entrada.
A complexidade depende do tamanho de entrada: os principais critérios são pior caso e caso médio. A complexidade de um algoritmo reflete o esforço para executá-lo sobre um conjunto de entradas (de um dado tamanho). A complexidade pessimista (ou no pior caso) da o valor máximo. A complexidade média (ou esperada) da o valor esperado: a média dos esforços, levando em conta a probabilidade de ocorrência de cada entrada.
– Complexidade no pior caso: Considera-se a instância que faz o algoritmo funcionar mais lentamente;
– Complexidade média: Consideram-se todas as possíveis instâncias e mede-se o tempo médio.
A complexidade pode ser calculada através do:
– Tempo de execução do algoritmo determinado pelas instruções executadas: quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n;
– Espaço de memória utilizado pelo algoritmo: quanto “espaço de memória/disco” é preciso para armazenar a(s) estrutura(s) utilizada(s) pelo algoritmo.
Medidas de Complexidade
O esforço realizado por um algoritmo é calculado a partir da quantidade de vezes que a operação fundamental é executada.
Para um algoritmo de ordenação, uma operação fundamental é a comparação entre elementos quando à ordem.

Referências Bibliográficas: * Complexidade de Algoritmos: Série Livros Didáticos Informática UFRGS - Vol. 13 - pag 14 – 15. * Disponível em: <http://www.inf.ufrgs.br/~prestes/Courses/Complexity/aula1.pdf>. Acesso em: 11 março