Atividade Supervisionada Linguagens Formais Teoria da Complexidade

Teoria da Computação
(Teoria da Complexidade)
Atividade Supervisionada
Professor: Sérgio Assunção Monteiro e-mail: [e-mail]
1.

Faça a análise de complexidade O para os algoritmos abaixo:

a. Insertion Sort
b. Selection Sort
c. Buble Sort
d. Heap Sort
e. Merge Sort
f. Quick Sort

2.

Conceitue as ordens de complexidade O, Θ e Ω.

3.
Faça uma análise comparativa da implementação iterativa e recursiva do algoritmo para geração da sequência da série de Fibonacci

4.
Compare a busca pelo menor elemento em uma lista não-ordenada com uma estrutura do tipo heap.
5.

Para o algoritmo abaixo, obter a ordem de complexidade para o caso médio:
Para i=1 até N faça
Para j= 1 até i*M faça a=1 6.

Faça a análise de complexidade O para os algoritmos abaixo:

a. Busca pelo menor elemento em uma estrutura heap
b. Somatório dos elementos ímpares de uma lista
c. Encontrar o maior número primo de uma lista

1

7.

Para o algoritmo abaixo, obter a ordem de complexidade para o caso médio:
Para i=1 até N faça
Para j= 1 até P faça inicio C[i,j]=0
Para k= 1 até N faça
Início
C[i,j]=C[i,j]+A[i,k]*B[k,j] fim//para k fim//para j

8.

Faça a análise de complexidade O para os algoritmos abaixo:
a. Inserção e exclusão em uma Pilha
b. impressão dos elementos de uma árvore binária

9.
Faça a análise de complexidade O para a busca do menor elemento em uma árvore
AVL, em uma lista não-ordenada e uma busca binária.
10.
Faça uma análise comparativa da implementação iterativa e recursiva do algoritmo para gerar a sequência de Fatorial.

2