APS_-_Complexidade_1

Prévia do material em texto

Atividade Supervisionada 
 
1. A atividade deve ser entregue individualmente no local apropriado do AVA 
2. As resoluções da atividade devem ser escritas em letra legível (as resoluções não podem ser 
digitadas) 
3. A atividade deve conter: 
1. Nome da disciplina: Complexidade de Algoritmos 
2. Código da Turma 
3. Nome e matrícula do aluno 
4. A data de entrega é até 07/04/2021. 
5. Esta atividade vai compor a nota da AV1. 
6. Todas as respostas devem ser justificadas. 
 
Questão 01: Preencha a tabela abaixo com o menor limite superior para as expressões dadas. 
 
Expressão O (...) 
7 + 0.001n 3 + 0.0025n4log n O (?) 
100n + 100n 1.5 + 5 log n O (?) 
0.3n + 5n 2.5 + 2.5 n2.75 O (?) 
n4 log n + n(log n)4 O (?) 
 
 
 
Questão 02: Obtenha a ordem de complexidade na notação big-Oh das seguintes operações de 
uma árvore binária ordenada e balanceada. 
(i) Imprimir todos os elementos da árvore 
Solução: 
 
(ii) Exclusão de um nó folha. 
Solução: 
 
 
Questão 03: Qual a fórmula fechada do somatório? 
∑(3𝑖 + 1)2 − (3𝑖 − 1)2
𝑛
𝑖=1
 
 
 
Solução: 
 
Questão 04: Qual a fórmula fechada do somatório? 
 
∑ log2 𝑖
𝑛
𝑖=1
 
Solução: 
 
Questão 05: Obtenha o valor do somatório para n=1000. 
 
 
∑
𝟏
𝒊(𝒊 + 𝟏)
𝒏−𝟏
𝒊=𝟏
 
Solução: 
 
 
Questão 06: O algoritmo de Dijkstra para obter o caminho mínimo em um grafo G=(V, A, w) 
dirigido ponderado tem muitas aplicações teóricas e práticas, onde V é o conjunto de vértices, A 
é o conjunto de arestas e w corresponde aos pesos de cada aresta. Supondo que w é 
representado pela matriz de adjacências e que G é um grafo completo, obtenha a 
complexidade de tempo para o algoritmo de Dijkstra para obter o caminho mínimo. 
 
Solução: 
 
 
Questão 07: 
 
Analisar, DETALHADAMENTE, a ordem de complexidade do algoritmo abaixo: 
K <- 1 
Para I <- 1 : N faça 
Início 
 K<- K * I 
 Para J <- 1 : K faça 
 Escreva( I ) 
 Fim_Para 
Fim_Para 
 
Solução: 
 
Questão 08: Qual a fórmula fechada do somatório? 
 
∑ 𝑘𝑎𝑘
𝑛
𝑘=1
 
Solução: 
 
Questão 09: Suponha que F é uma função definida no conjunto {20, 21, 22, 23, …} sobre a qual 
sabe-se apenas que 
 F(1) = 1 e 
 
 F(n) = 2 F(n/2) + 7n + 2, para n ≥ 2 
para n = 21, 22, 23, 24, etc. A fórmula fechada para F é: 
 
Solução: 
 
 
Questão 10 
Utilizando o Teorema Mestre, obtenha a fórmula fechada da expressão: 
T(n) = 4 T(n-1) + n, para n ≥ 2 
T(1) = 1 
 
Solução: