A Complexidade de Algoritmos

[pic 1]

FACULDADE ANHANGUERA DE JUNDIAÍ

CURSO DE CIÊNCIA DA COMPUTAÇÃO

KETTULHY MENDES, RA: 4200053633

CHRISTIAN SANTOS GROSSI, RA: 4200053640.

HENRIQUE TORRES, RA: 4252066478.

ANÁLISE E COMPLEXIDADE DE ALGORITIMOS

JUNDIAÍ

2015

KETTULHY MENDES

CHRISTIAN SANTOS GROSSI

HENRIQUE TORRES

                                ANÁLISE E COMPLEXIDADE DE ALGORITIMOS

Atividade Supervisionada com o objetivo de aprovação na disciplina de Complexidade de Algoritmos do curso de Ciência da computação na Faculdade Anhanguera de Jundiaí, sob a orientação do Professor Rodrigo Rocha.

JUNDIAÍ

2015

KETTULHY MENDES

CHRISTIAN SANTOS GROSSI

HENRIQUE TORRES

ANÁLISE E COMPLEXIDADE DE ALGORITIMOS

Atividade Supervisionada com o objetivo de aprovação na disciplina de Complexidade de Algoritmos do curso de Ciência da computação na Faculdade Anhanguera de Jundiaí, sob a orientação do Professor Rodrigo Rocha.

Aprovado em 09 de Abril de 2015

BANCA EXAMINADORA

____________________________________

Professor Rodrigo Rocha.

Anhanguera Educacional Ltda.

RESUMO

O objetivo deste trabalho é elaborar estudo sobre análise de classes distintas de algoritmos: algoritmos de ordenação, algoritmos em grafos, algoritmos interativos e recursivos e algoritmos gulosos através de medidas de complexidade.

Foi elaborado as medidas assintóticas de complexidade, considerando que os algoritmos são representados, muitas vezes, por funções matemáticas, assim, fez-se um estudo sobre o comportamento assintótico dessas funções.

Palavras-Chave: Algoritmos, funções, ordenação.

ABSTRACT

The objective of this work is to elaborate study on analysis of different classes of algorithms: sorting algorithms, algorithms on graphs, interactive and recursive algorithms and greedy algorithms through complexity measures.

Was prepared the asymptotic measures of complexity, whereas the algorithms are represented often by mathematical functions, as well, there was a study of the asymptotic behavior of these functions.

Keywords: Algorithms, functions, sorting.

SUMÁRIO

1. INTRODUÇÃO.........................................................................................................7

2. RELATÓRIO 1………………..................................................................................8

3. RELATÓRIO 2………………................................................................................11

4. CONCLUSÃO..........................................................................................................13

1. INTRODUÇÃO

O desafio proposto foi 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 são importantes para serem aplicadas em situações de decisão entre dois ou mais algoritmos que resolvem certos tipos de problemas.

Fez-se um estudo sobre o comportamento assintótico de funções. Foi-se analisado algoritmos de ordenação por seleção e por inserção.

Foi realizada a análise de desempenho de alguns algoritmos clássicos de busca, ordenação e sobre grafos. Como também as Medidas de Complexidade, análise assintótica de limites de complexidade.

2. RELATÓRIO 1

Passo 2: Definir, as medidas de complexidade Ômicron (Ο), Ômega (Ω) e Theta (Θ).

1) Melhor Caso
Definido pela letra grega Ω (Ômega).

Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n.
Ex: f(n)=Ω(1)

2) Pior Caso
 Representado pela letra grega 0 (Ômicron).

 Baseia-se no maior tempo de execução sobre todas as entradas de tamanho n.
 É o método mais fácil de se obter.
 Ex: f(n)=0(1)

3) Médio Caso
 Definida pela letra grega Ɵ(Theta).

 Deve- se obter a média dos tempos de execução de todas as entradas de tamanho n, ou baseado em probabilidade de determinada condição ocorrer.
 Ex: f(n)=Ɵ(n/2)

Passo 3: Usar as medidas de complexidade descritas acima e fazer as seguintes atividades:

1) Comparar uma função Linear f(n) com uma função Quadrática g(n).
Função Linear f(n) = 5n +2
 Função Quadrática g(n) = 2n²

f(n)= 5n+2
g(n)=2n²
f(n) é o(g(n))?
Para n ≥ 3 é o(g(n)).

2) Comparar uma função exponencial f(n) com uma função cúbica g(n).
Função exponencial f(n) = 2n n
Função cúbica g(n) = n³+2n

f(n)=2n n
g(n)= n³+2n
f(n)Ω(g(n))?
Para n ≥ 5 é Ω(g(n).