Ações práticas controladas - análise e complexidade de algoritmos

Anhanguera Educacional

Ciência da Computação

Atividades Práticas Supervisionadas - Análise e Complexidade de Algoritmos

Rafal Henrique Berro

Luan Sousa

Vitor Lellis

Santa Bárbara d'Oeste

2014

Rafal Henrique Berro

Luan Sousa

Vitor Lellis

Atividades Práticas Supervisionadas - Análise e Complexidade de Algoritmos

Monografia apresentada como exigência para obtenção do grau de Especialização em Ciência da Computação da Anhanguera Educacional.

Orientador: Thiago Salhab

Santa Bárbara d'Oeste

2014

RESUMO

De acordo com Ziviani (2005), um algoritmo pode ser visto como uma sequência de

ações executáveis a fim de obter uma solução para um determinado tipo de problema. O

objetivo da disciplina de Análise e Complexidade de Algoritmos é atribuir ferramentas que

auxiliem na decisão de escolha entre dois ou mais algoritmos, qual é o melhor para resolver

determinado problema, levando em consideração o tempo gasto para executar todas as ações

e a quantidade de memória utilizada para armazenamento das informações. O estudo da

complexidade é feita através de classes assintóticas.

Esse desafio propõe aos alunos fazerem um estudo sobre análise de classes distintas

de algoritmos, sendo elas: algoritmos de ordenação, algoritmos em grafos, algoritmos

iterativos e recursivos e algoritmos gulosos, fazendo uso dos conceitos de medidas de

complexidade vistos na disciplina de Análise e Complexidade de Algoritmos. Essas análises

serão feitas para que o aluno possa aplicá-las em situações de decisão entre dois ou mais

algoritmos que resolvem certos tipos de problemas.

O objetivo do desafio é mostrar ao aluno o funcionamento das classes de algoritmos

citadas acima e, ao final conhecer uma ferramenta que o ajudará na análise de complexidade.

Palavras-chave: ATPS,CCOMP,ANHANGUERA,COMPLEXIDADE

SUMÁRIO

ETAPA 1, PASSOS 2 e 3 4

ETAPA 1 PASSO 4 5

REFERÊNCIAS 7

ETAPA 1

PASSO 2

Ômicron(O)

A sua medida de complexidade é considerada de pior caso, se baseia em um maior(pior) tempo de execução sobre as entradas no tamanho N. Em uma busca linear, o pior caso acontece quando o elemento procurado está na última posição da lista. Dessa forma a complexidade é dada por O(N).

Theta

Considerado complexidade de médio caso, dos três é o mais difícil de se determinar porque necessita da média dos tempos de execução de todas as entradas de tamanho N.

Ômega

Possui o menor tempo de