ALGORITMOS AULA 02

Prévia do material em texto

Protocolos de Redes e de Computadores
AULA 02
ALGORITMOS AVANÇADOS – AULA 02
Prof. Msc. Alexandre José Braga da Silva
alex.professor@gmail.com
CCT0312 – Algoritmos Avançados
Objetivos da Aula:
• Relembrar o conceito de Ponteiros;
• Relembrar o conceito de passagem de parâmetros;
• Entender o conceito de Análise de Algoritmo;
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Ponteiros guardam endereços de memória. Quando você anota o 
endereço de um colega você está criando um ponteiro. O ponteiro é o 
seu pedaço de papel.
Um ponteiro também tem tipo, eles indicam locais cujos conteúdos 
são diferentes. Então dois endereços são ponteiros de tipos 
diferentes.
No C++ quando declaramos ponteiros nós informamos ao compilador 
para que tipo de variável vamos apontá-lo. Um ponteiro int aponta 
para um inteiro, isto é, guarda o endereço de um inteiro.
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Para declarar um ponteiro temos a seguinte forma geral:
tipo_do_ponteiro *nome_da_variável;
É o asterisco (*) que faz o compilador saber que aquela variável vai 
guardar um endereço para aquele tipo especificado. Vamos ver 
exemplos de declarações:
int *pt; → declara um ponteiro para um número inteiro.
char *temp,*pt2; → declara dois ponteiros para caracteres. 
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Eles ainda não foram inicializados. Isto significa que eles apontam 
para um lugar indefinido.
Usar o ponteiro nestas circunstâncias pode levar a um travamento do 
computador. O ponteiro deve ser inicializado antes de ser usado!
Para atribuir um valor a um ponteiro recém-criado poderíamos igualá-
lo a um valor de memória. Mas, como saber a posição na memória de 
uma variável do nosso programa?
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Podemos então deixar que o compilador faça este trabalho por nós. 
Para saber o endereço de uma variável basta usar o operador &. Veja 
o exemplo:
int cont=10;
int *pt;
pt=&cont;
Criamos um inteiro com o valor 10 e um apontador para um inteiro pt. 
A expressão &cont nos dá o endereço de cont, o qual armazenamos 
em pt. Repare que não alteramos o valor de cont, que continua 
valendo 10.
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Podemos, por exemplo, alterar o valor de cont usando pt. Para tanto 
vamos usar o operador "inverso" do operador &. que é o operador *.
No exemplo anterior, uma vez que fizemos pt=&cont a expressão 
*pt é equivalente ao próprio cont. Isto significa que, se quisermos 
mudar o valor de cont para 12, basta fazer *pt=12. Vejamos dois 
exemplos de utilização de ponteiros:
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
#include <iostream>
#include <conio.h>
using namespace std;
int main (){
int num,valor;
int *p;
num=55;
p=&num; /* Pega o endereco de num */
valor=*p; /* Valor e igualado a num de uma maneira indireta */
cout<<"Valor: "<<valor<<endl;
cout<<"Endereco para onde o ponteiro aponta: "<<p<<endl;
cout<<"Valor da variavel apontada: "<<*p<<endl;
}
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Passagem de parâmetros por valor: 
A função recebe uma cópia da variável que é fornecida quando é 
invocada. Todas as alterações feitas dentro da função não vão afetar os 
valores originais.
Passagem de parâmetros por referência: 
Neste caso o que é enviado para a função é uma referência às variáveis 
utilizadas, e não uma simples cópia, pelo que as alterações realizadas 
dentro da função irão certamente alterar os valores contidos nessas 
variáveis.
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Exemplo de passagem de parâmetros por valor: 
#include<iostream>
using namespace std;
void troca(int a, int b){
int temp;
temp=a;
a=b;
b=temp;
}
int main(){
int a=2,b=3;
cout<<"Antes de chamar a funcao: 
\na="<<a<<"\tb="<<b<<endl;
troca(a,b);
cout << "\Depois de chamar a funcao: 
\na="<<a<<"\tb="<<b<<endl;
}
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Exemplo de passagem de parâmetros por referência: 
#include<iostream>
using namespace std;
void troca(int &a, int &b){
int temp;
temp=a;
a=b;
b=temp;
}
int main(){
int a=2,b=3;
cout<<"Antes de chamar a funcao: 
\na="<<a<<"\nb="<<b<<endl;
troca(a,b);
cout<<"Depois de chamar a funcao: 
\na="<<a<<"\nb="<<b<<endl;
}
CCT0312 – Algoritmos Avançados
Análise de Algoritmos:
A análise de algoritmos estuda a correção e o desempenho de 
algoritmos. Procura respostas para perguntas do seguinte tipo:
 Este algoritmo resolve o meu problema?
 Quanto tempo ele consome para processar uma entrada n?
 A análise de algoritmos estuda paradigmas: divisão e 
conquista, programação dinâmica, busca local, aproximação, 
etc.
CCT0312 – Algoritmos Avançados
Etapas para Análise de Algoritmos:
 Correção
 Analise o pior caso
 Enfoque o termo principal do tempo de execução
 Melhore a ordem de magnitude
 Reduza os fatores constantes
CCT0312 – Algoritmos Avançados
Análise Assintótica:
Também conhecida como Ordem O ou Big-O, é uma análise de 
algoritmos que se concentra em valores enormes para 
algoritmos complexos. Nessa matemática, as funções são 
classificadas em ordens; todas as funções de uma mesma 
ordem são equivalentes. 
As cinco funções mostradas abaixo, por exemplo, pertencem à 
mesma ordem:
n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n
CCT0312 – Algoritmos Avançados
Ordem O:
Dadas funções assintoticamente não negativas f e g, dizemos que f 
está na ordem Ο de g e escrevemos f = Ο(g) se f(n) ≤ c · 
g(n) para algum c positivo e para todo n suficientemente grande. 
Em outras palavras, existe um número positivo c e um número n0 tais 
que f(n) ≤ c · g(n) para todo n maior que n0.
Obs.: A notação Ο empregada nesta definição é conhecida como 
notação assintótica ou notação de Landau.
CCT0312 – Algoritmos Avançados
Ordem O:
Exemplo 1: 
Se f(n) ≤ 9999 g(n) para todo n ≥ 1000 então f = Ο(g). 
Exemplo 2: Suponha que f(n) = 2n² + 3n + 4 e g(n) = n². Observe que
2n2 + 3n + 4 ≤ 2n2 + 3n2 + 4n2 = 9n2
desde que n ≥ 1. Resumindo, f(n) ≤ 9 g(n) para todo n ≥ 1. Portanto, 
f(n) = Ο(g(n)).
CCT0312 – Algoritmos Avançados
Ordem O:
A notação O ajuda a calcular a função de custo para algoritmos 
complexos e grandes processamentos de dados.
A definição formal da notação O não é usada diretamente. A notação 
O de uma função f é entregue pelas regras de simplificação a seguir:
 Se f(x) é a soma de vários termos, o que possuir maior taxa de 
crescimento é mantido, e todos os outros são omitidos.
 Se f(x) é um produto de diversos fatores, quaisquer constantes 
(termos do produto que não depende de x) são omitidos.
CCT0312 – Algoritmos Avançados
Ordem O:
Exemplo de uso na computação: a operação da soma O(f(n)) + O(g(n)) 
pode ser usada para calcular o tempo de execução de uma sequência 
de trechos de programas. 
Considere três trechos de programas com tempos de execução O(n), 
O(n.n) e O(n . log . n). Logo, o tempo de execução dos dois primeiros 
trechos de programa é o O(máx(n, n.n)), que é O(n.n).
Portanto, o tempo de execução final dos três trechos é O(máx(n.n, n . 
log . n), que é O(n.n).
CCT0312 – Algoritmos Avançados
Ordem O:
Resumindo: Big-O descreve o comportamento geral do algoritmo em 
termos do crescimento do número de operações conforme cresce o 
número de elementos processados (n).
Usamos a letra O seguida de uma função sobre n que descreva esse 
crescimento do algoritmo. Quanto mais rapidamente crescer as 
operações para processar os itens, "pior" é o desempenho do 
algoritmo (pois ele executa mais instruçõese, portanto, demora mais).
O gráfico a seguir ilustra as curvas de crescimento mais comuns. 
CCT0312 – Algoritmos Avançados
Ordem O:
CCT0312 – Algoritmos Avançados
Ordem O:
Complexidade O(n!) (fatorial) → o número de instruções executadas 
cresce muito rapidamente para um pequeno crescimento do número 
de itens processados. 
É o pior comportamento para um algoritmo, pois rapidamente o 
processamento se torna inviável. Exemplo: um algoritmo que gere 
todas as possíveis permutações de uma lista.
CCT0312 – Algoritmos Avançados
Ordem O:
Complexidade O(2n) (exponencial) → também é bem ruim, pois o 
número de instruções também cresce muito rapidamente, ainda que 
numa taxa menor do que o anterior. Exemplo: algoritmos que fazem 
busca em árvores binárias não ordenadas.
Complexidade O(n2) (quadrático) → é factível, mas tende a se tornar 
muito ruim quando a quantidade de dados é suficientemente grande. 
Exemplo: algoritmos que têm dois laços (for) encadeados, como, por 
exemplo, o processamento de itens em uma matriz bidimensional.
CCT0312 – Algoritmos Avançados
Ordem O:
Complexidade O(n log n) → é melhor do que o quadrático, sendo 
geralmente até onde se consegue otimizar algoritmos que são 
quadráticos. Exemplo: algoritmo de ordenação QuickSort (que tem 
essa complexidade no caso médio, mas que ainda assim é 
quadrático no pior caso).
Complexidade O(n) (linear) → é aquele cujo crescimento no número 
de operações é diretamente proporcional ao crescimento do número 
de itens. Exemplo: algoritmos de busca em uma matriz 
unidimensional não ordenada.
CCT0312 – Algoritmos Avançados
Ordem O:
Complexidade O(log n) (logaritmo) → é aquele cujo crescimento do 
número de operações é menor do que o do número de itens. 
Exemplo: algoritmos de busca em árvores binárias ordenadas (no 
caso médio, no pior caso continua sendo linear).
Complexidade O(1) (constante) → é aquele em que não há 
crescimento do número de operações, pois ele independente do 
volume de dados de entrada (n). Exemplo: acesso direto a um 
elemento de uma matriz.
CCT0312 – Algoritmos Avançados
Ordem O:
Exemplo prático: Calcular o custo do algoritimo usado para encontrar 
o maior elemento de uma matriz n x n:
void maiorElemento (int vetor [ ], int matriz[ ][ ] ) {
 int i, j;
 for (i=0; i < matriz.length; i++) { // i=0 … i=n (n+1).2
 vetor[i] = matriz[i][0]; // n
 for (j=0; j<matriz[i].length; j++) { // j=0 … j=n n.(n+1).2
 if (matriz[i][j] > vetor [i]) // n . n
 vetor[i] = matriz [i][j]; // pior caso=n.n melhor caso: 0
 }
 }
}
CCT0312 – Algoritmos Avançados
Ordem O:
Melhor caso:
0
n.(n+1).2 → 2n2 + 2n
n
(n+1).2 → 2n + 2
C(n) = 2n
2 + 5n + 2
Pior caso:
n . n → n2
n.(n+1).2 → 2n2 + 2n
n
(n+1).2 → 2n + 2
C(n) = 3n
2 + 5n + 2
Complexidade O(n2)
CCT0312 – Algoritmos Avançados
Ordem O:
Exemplo prático: Calcular o custo do algoritimo abaixo:
void calculo (int vetor [ ]) {
 const n = vetor.length; // n
 for (int i=0, i < n; i++) { // (n+1).2
 console.log(n); // n
 }
}
Complexidade O(n)
CCT0312 – Algoritmos Avançados
Ordem O:
Exemplo de algoritmos complexos:
O(n) → Busca em um vetor ordenado ou não ordenado.
O(n2) → Busca em uma árvore multidimensional.
O(log n) → Localizar um item em uma árvore de busca balanceada.
O(log n!) → Realizar uma transformada de Fourier rapidamente.
O(n!) → Resolver o problema do “Caixeiro viajante” usando o 
método da “força bruta”.
CCT0312 – Algoritmos Avançados
Ordem O - Exercícios:
1. Um algoritmo de busca binária em um vetor A, temos: um conjunto 
de valores previamente armazenados, nas posições A[i], A[i+1], ... 
A[n], em ordem crescente. Verificar se um número V qualquer está 
entre este conjunto de valores. Se o número V procurado não for 
encontrado o algoritmo deve retornar -1. Caso contrário, deve 
retornar a posição no vetor A que contém o número V.
a) desenvolver o algoritmo proposto e;
b) calcular a complexidade para o melhor caso e pior caso para o 
algoritmo proposto.
CCT0312 – Algoritmos Avançados
Ordem O - Exercícios:
a) int buscaBinaria (int x, int n, int A[]){
 int v= -1;
 while (v < x-1) {
 int m = (v-x)/2;
 if (A[m]<x)
 v = m;
 }
 return v;
 }
CCT0312 – Algoritmos Avançados
Ordem O - Exercícios:
b) MELHOR CASO: o número está no meio do vetor → O(1).
 
 PIOR CASO: o número não está no vetor. Como a busca ocorre 
 sempre na metade do vetor e o algoritmo quebra sucessivamente 
 o vetor ao meio até 1, temos uma sequencia: n, n/2, n/22 ... 1. 
 Assim, a sequencia v = log n → O(log n)
CCT0312 – Algoritmos Avançados
Ordem O - Exercícios:
2. Analise o pior caso do algoritmo abaixo que calcula o valor de nn.
int funcao(int n) {
 int i, r;
 r = 1;
 for (i=1; i<=n; i++)
 r = r * n;
 return r;
}
→ n
→ (n+1) . 2
→ n
C(n) = 3 . n + 1 → C(n)
Complexidade O(n)
CCT0312 – Algoritmos Avançados
Ordem O - Exercícios:
3. Analise o pior caso do algoritmo abaixo:
int funcao(int n) {
 int a, b, c, r;
 b = n; c = n; r = 1;
 while (b >= 1) {
 a = b % 2;
 if (a == 1)
 r = r * c;
 c = c * c * c;
 b = b /2;
 }
 return r;
}
→ n
→ n + (log n)
→ n
→ n (pior caso) 
→ n
C(n) = 5 . n + log n 
Complexidade O(log n)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33