01.ED.IntroduçãoComplexidade-2014-3

Prévia do material em texto

DCC013 
 
Estrutura de Dados 
Introdução 
Análise de Complexidade 
Estrutura de Dados - Ementa 
2 
1. Introdução – Análise de Complexidade. 
2. Tipos Abstratos de Dados. 
3. Matrizes. 
4. Listas. 
5. Pilhas e Filas. 
6. Árvores. 
7. Ordenação e Recuperação de Informação. 
8. Grafos. 
Site de ED e Lab. II: 
http://sites.google.com/site/edlab2ufjf/ 
 
Bibliografia básica 
• “Estrutura de Dados e Algoritmos em 
C++”. 
 AdamDrozdek 
 Cengage Learning, 2002. 
 
• "Introdução a Estruturas de Dados 
com técnicas de programação em C“ 
 W. Celes, R. Cerqueira, J. Rangel 
 Editora Elsevier/Campus, 2004 
 
 
3 
Bibliografia básica 
• “Algoritmos em Linguagem C“ 
Paulo Feofiloff 
 Editora Elsevier/Campus 
 
• “Projeto de Algoritmos com 
Implementações em Java e C++”. 
Nivio Ziviani 
 Thomson, 2003 
 
 
 
4 
Bibliografia complementar 
 "Objetos, Abstração, Estruturas de Dados e 
Projetos usando C++", Koffman & Wolfgang, 
Gen LTC. 
 “The art of computer programming v. 1 - 
Fundamental Algorithms”, D. E. KNUTH. 
Addison-Wesley, 1972. 
 “Estrutura de Dados e Seus Algoritmos”. J. L. 
Szwarcfiter. Segunda Edição. LTC, 1994. 
 
 
 
5 
Introdução 
“Programação é a arte de construir e formular 
algoritmos de uma forma sistemática”. 
“Algoritmos + Estruturas de Dados = Programas”. 
Recomendação Importante: Revisão de 
Construção de Algoritmos / Programas 
6 
 Representação de dados em um programa: 
Constante (valor) ou Variável (nome e valor) 
Introdução 
 Tipo de Dados: todo valor (constante ou variável) 
de um programa tem um tipo associado que 
determina o conjunto de valores (domínio de 
dados) que podem ser assumidos e o conjunto de 
operações a que pode ser submetido. 
 Exemplos de Tipos de Dados Básicos: inteiro 
(ou int), real, caracter (ou car) e lógico 
(ou log). 
7 
 int 
 Domínio: conjunto dos inteiros. 
Operações: usam dois argumentos inteiros e, de 
acordo com o resultado, são: 
 +, -, *, div, e mod: resultado int 
 /: resultado real 
 <, ≤, =, >, ≥ e ≠: resultado log 
 real 
Domínio: conjunto dos reais. 
Operações: usam dois argumentos reais e, de 
acordo com o resultado, são: 
 +, -, * e /: resultado real 
 <, ≤, =, >, ≥ e ≠: resultado log 
 
8 
Introdução 
 car 
 Domínio: conjunto de caracteres alfanuméricos. 
 Operações: usam dois argumentos do domínio e 
 fornecem resultado log: <, ≤, =, >, ≥ e ≠ 
 log 
 Domínio: {verdadeiro, falso}. 
 Operações: usam dois argumentos do domínio e 
fornecem resultado log: 
Conectivos lógicos: conjunção (e, ^), disjunção 
(ou, ), disjunção exclusiva (xou, ), negação 
(não, ). A negação trabalha com somente um 
argumento. 
Conectivos relacionais: = e . 
9 
Introdução 
 Declaração de Variáveis – Sintaxe: tipo 
nome(s); 
 Implicações da declaração de uma variável: 
 Alocação de um espaço na memória que possa 
conter um valor do seu tipo. 
 Associação do endereço dessa posição da memória 
ao nome da variável. 
 Declarada uma variável, toda vez que ela for 
referenciada em qualquer comando do programa, 
o computador vai trabalhar com o conteúdo de seu 
endereço, que é o valor da variável. 
10 
Introdução 
 Algoritmos demandam tempo de execução e 
recursos (memória, espaço em disco, dispositivos 
externos, etc). 
 Analisar a alocação de recursos que um certo 
algoritmo demanda é importante na escolha de 
soluções mais rápidas ou que ocupem menos 
espaço de memória, por exemplo. 
 Bons programadores se preocupam em 
implementar algoritmos que demandam o mínimo 
de recursos e executem no menor tempo possível. 
Análise de Complexidade 
11 
Embora um programa possa ser analisado sob vários 
aspectos, destaca-se a seguir a análise relativa ao seu 
desempenho, especialmente, em relação a medida do seu 
tempo de computação. 
Seja um programa com x instruções: 
Tempo total = [(tempo de execução da instrução i) x 
 (número de vezes que a instrução i é executada)] 


x
i 1
Como o tempo de execução da instrução i é sempre de difícil 
obtenção, avalia-se o tempo total considerando somente o 
número de vezes que a instrução é executada. Esse número é 
chamado de contagem de freqüência ou simplesmente 
freqüência da instrução i. 
12 
Análise de Complexidade 
Exemplos de determinação de freqüência de uma instrução: 
• Um comando que pertencente a uma sequência simples: 
... 
X = X + 1; tem frequência f = 1 
... 
• Se essa instrução pertencer ao domínio de uma estrutura de 
repetição: 
for (I = 1; I <= N; I++){ 
 ... 
 X = X + 1; ela passa a ter frequência f = = N 
 ... 
} 


N
i 1
1
13 
Análise de Complexidade 
• Se a estrutura do exemplo anterior pertencer a outra 
iteração: 
A maior freqüência encontrada num programa é chamada de 
ordem de grandeza de crescimento de tempo do programa. 
for(J = 1; J <= N; J++){ 
 ... 
 for(I = 1; I <= N; I++){ 
 ... 
 X = X + 1; passa a ter frequência f = = N2 
 ... 
 } 
 ... 
} 

 
N
j
N
i1 1
1
A ordem de grandeza de um algoritmo é o principal 
parâmetro para análise do desempenho de sua execução. 
14 
Análise de Complexidade 
As ordem de grandeza mais comuns nos algoritmos são: 
O parâmetro N caracteriza a quantidade de entradas, a 
quantidade de saídas, a soma dessas quantidades ou a grandeza 
de uma delas. 
•O (1)  tempo de computação constante 
•O (log2 N)  tempo logaritmo 
•O (N)  linear 
•O (N log2 N) 
•O (N2)  quadrática 
•O (N3)  cúbica 
•O (2N)  exponencial 
Aplicação: Analisar a solução iterativa de um algoritmo que leia 
um valor inteiro N, calcule e imprima o seu fatorial. Se o valor 
lido para N for negativo, imprimir uma mensagem de erro. 
0 2 4 6 8 10
0
500
1000
1500
N
Te
m
po
N3
2N
N2
15 
Análise de Complexidade 
 #include<stdio.h> 
 int main() 
 { 
 int N, FAT = 1, C; 
1 printf("Digite N"); 
2 scanf("%d",N); 
3 if(N >= 0){ 
4 for(C = 1; C <= N; C++) 
5 FAT = FAT * C; 
6 printf("Fatorial de %d = %d", N, FAT); 
 } 
 else 
7 printf("Valor negativo lido"); 
 } 
Uma solução poderia ser: 
Análise de Complexidade 
16 
Comando N < 0 
1 1 
2 1 
3 1 
4 0 
5 0 
6 0 
7 1 
Total 4 
17 
Análise de Complexidade 
Comando N < 0 N = 0 
1 1 1 
2 1 1 
3 1 1 
4 0 1 
5 0 0 
6 0 1 
7 1 0 
Total 4 5 
Análise de Complexidade 
18 
Comando N < 0 N = 0 N = 1 
1 1 1 1 
2 1 1 1 
3 1 1 1 
4 0 1 2 
5 0 0 1 
6 0 1 1 
7 1 0 0 
Total 4 5 7 
Análise de Complexidade 
19 
Comando N < 0 N = 0 N = 1 N > 1 
1 1 1 1 1 
2 1 1 1 1 
3 1 1 1 1 
4 0 1 2 N + 1 
5 0 0 1 N 
6 0 1 1 1 
7 1 0 0 0 
Total 4 5 7 2N + 5 
Análise de Complexidade 
20 
Soma das frequências = 2N + 5 
 
Desconsiderando as constantes e os termos de 
menor ordem, conclui-se que o programa possui 
complexidade O(N). 
Análise de Complexidade 
21 
22 


n
i
ix
0
 Analisar o tempo de processamento de um 
programa para calcular o seguinte somatório 
(série geométrica): 
float Soma1(int x, int n) 
{ 
 int soma = 0; 
 for(int i=0; i<=n; i++){ 
 int prod = 1; 
 for(int j=0; j<i; j++) 
 prod = prod*x; 
 soma = soma + prod; 
 } 
 return soma; 
} 
Vezes 
 
1 
n+2 
n+1n+1 
 
1 


n
i
i
0
  6
2
7
2
2

nn
nT
ordem de grandeza = O(n2) 
Análise de Complexidade 
23 
     xxxxxxxx n
n
i
i 

111111 2
0
 Regra de Horner 
float Soma2(int x, int n) 
{ 
 int i, soma = 0; 
 for(i=0; i<=n; i++){ 
 soma = soma*x +1; 
 } 
 return soma; 
} 
Vezes 
 
1 
n+2 
n+1 
 
1 
  52  nnT
ordem de grandeza = O(n) 
Análise de Complexidade 
24 
1
11
0 





x
x
x
nn
i
i
 Fórmula fechada: 
float Soma3(int x, int n) 
{ 
 return (pot(x,n+1) – 1)/(x – 1); 
} 
 Função para potência: pot(int x, int n) 
com complexidade T(n) = log2(n) + 2 
    21log2  nnT
ordem de grandeza = O(log2(n)) 
Análise de Complexidade 
25 
 Comparando as três soluções apresentadas: 
    21log2  nnT
  52  nnT
Programa 
 Soma 1 O(n2) 
 Soma 2 O(n) 
 Soma 3 O(log2(n)) 
  6
2
7
2
2

nn
nT
Análise de Complexidade 
26 
 Comparando as três soluções apresentadas: 
Programa 
 Soma 1 O(n2) 
 Soma 2 O(n) 
 Soma 3 O(log2(n)) 
Análise de Complexidade 
0 2 4 6 8 10 11
0
10
20
30
40
50
60
70
80
90
100
 
 
soma1
soma2
soma3
 A tabela abaixo representa possíveis valores 
temporais para cada ordem de grandeza de 
complexidade 
Análise de Complexidade 
27 
 Algumas ordens de grandeza de complexidade 
tornam proibitivo a aplicabilidade do algoritmo, 
devendo ser usado apenas quando não se 
conheça solução de menor complexidade. 
Análise de Complexidade 
28 
1. Calcular xn e determinar a complexidade da sua 
solução. 
2. Qual a complexidade das funções f, g e h? 
 
Exercícios 
int f(int n){ 
 int soma=0; 
 int i=1; 
 for(i=1; i<=n; ++i){ 
 soma += 1; 
 } 
 return soma; 
} 
29 
2. Qual a complexidade das funções f, g e h? 
 
Exercícios 
int h(int n){ 
 return f(n) + g(n); 
} 
int g(int n){ 
 int soma=0; 
 int i=1; 
 for(i=1; i<=n; ++i){ 
 soma += i + f(i); 
 } 
 return soma; 
} 
30 
1. Duas soluções são possíveis: 
Solução O(n): 
 
 
Solução O(log2n): 
 
2. O(f(n)) = O(n) 
 O(g(n)) = O(n2) 
 O(h(n)) = O(f(n) + g(n)) = O(n + n2) = O(n2) 
Respostas 









 0 ,
0 ,1
1 nsexx
nse
x
n
n
 
  













ímparén,, n)x(x
parénnx
nse
x
n
nn
 0
 ,0,)(
0 ,1
2/2
2/2
31