100%
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
AEDSII_aula_001_linguagem_C.pdf
Algoritmos e
Estruturas de Dados II
Aplicação de Algoritmos
Ordenação
Pesquisa
Referências
N. Ziviani. Projeto de Algoritmos com Implementações em
Pascal e C. Cengage Learning, São Paulo, SP, 2011.
R. Sedgewick. Algorithms in C, Parts 1-4 (Fundamental
Algorithms, Data Structures, Sorting, Searching). Addison-
Wesley, 1997.
Ementa
• Tipos Abstratos de Dados (TADs)
• Análise de Algoritmos
O(n), O(n log n), )(n!), ...
• Estruturas de dados
listas, filas e pilhas
• Métodos de ordenação
quick, heap, merge, select, etc
• Métodos de pesquisa
hash, árvores, árvores binárias,
árvores digitais
Parte 1
Parte 2
Parte 3
Avaliação
• 3 provas (total 60 pontos)
• trabalhos práticos – 40 pontos (TP0 + 2 TPs)
• Implementação
• Documentação
• Teste
Regras Gerais
Exame especial (nota >= 40 && frequencia >= 75%).
Prova de reposição
Apenas para aqueles que perderam uma prova.
Monitoria - horário de atendimento:
(em breve)
Presença:
Verificada por meio de chamada
Moddle / Website
• Todas informações relacionadas ao curso, incluindo notas de
aulas, estarão disponíveis no Moodle, fórum
• PRATICO: Sistema de submissão de trabalhos práticos
http://aeds.dcc.ufmg.br
Detalhes
• Linguagem: C
• Software Recomendado: CodeBlocks (www.codeblocks.org)
• http://wiki.codeblocks.org/index.php?title=Creating_a_new_project
• Alta carga extra classe
• Não utilizar bibliotecas do windows
• Manual de instalação:
• http://wiki.codeblocks.org/index.php?
title=Installing_Code::Blocks
Code::blocks
Alternativa
Sempre pode usar gcc + vi (emacs) + gdb
Tópicos
• Indentação
• Comentários
• Modularização
• Compilação e Debug
• Entrada e saída
• Vetores e Strings
• Passagem de parâmetros
• Structs
Linguagem C
Boas
Prá)cas
• Com
um
pequeno
esforço
extra,
programas
escritos
em
C
podem
se
tornar
mais
legíveis
e
mais
facilmente
“debugáveis”
• No
caso
de
disciplinas
de
programação,
isso
ainda
ajuda
no
entendimento
das
idéias
e
na
correção
de
trabalhos
Indentação
• É
usual
empregar
TABS
para
indicar
blocos
de
programação
– Em
geral,
1
tab
equivale
a
8
espaços,
MAS
NÃO
USAR
ESPAÇOS
para
alinhar
• Há
vários
es)los
• Quando
o
bloco
é
longo,
é
usual
colocar
um
pequeno
comentário
após
o
fechamento
indicando
o
que
está
sendo
fechado
Indentação
• K&R:
Kernighan
&
Ritchie
Indentação
• 1TBS:
One
True
Brace
Style
Indentação
• Allman
Comentários
• Importantes
para
compreensão
do
código
• Mais
importantes
em
código
mais
complexo
• Úteis
para
explicar
o
conteúdo
de
variáveis,
mas
não
subs)tuem
um
bom
critério
de
atribuição
de
nomes
• Não
exagerar!
Comentários
• No
início
de
cada
módulo
de
código
(arquivos
.c,
.h)
• Uma
linha
em
cada
função,
explicando
o
que
ela
faz
– Não
é
necessário
explicar
COMO
ela
faz,
o
código
deve
ser
claro
o
bastante
para
permi)r
esse
entendimento
em
uma
função
razoavelmente
pequena
– Se
necessário,
considerar
a
quebra
em
outras
funções
• Comentário
na
linha
da
declaração,
se
necessário,
para
esclarecer
o
significado/o
uso
de
uma
variável
• Comentário
na
linha
do
fecha-‐chave,
para
ajudar
a
entender
blocos
e
loops
Comentários
• No
início
de
um
bloco/arquivo
fonte
Comentários
• Em
função
(simples)
Comentários
• Em
funções
(arquivo
.h)
Comentários
• Em
variáveis
• Em
structs
Comentários
• No
fim
de
um
bloco
de
programa
• No
código
Modularização
• Planejar
a
quebra
de
um
programa
em
módulos
– Um
módulo
não
significa
necessariamente
um
arquivo
fonte;
muitas
vezes,
é
um
par
de
arquivos
.c
/
.h
– Existe
sempre
um
arquivo
fonte
para
o
programa
principal
(main),
e
outros
para
funções
adicionais
ou
componentes
• Montar
módulos
especificamente
para
)pos
abstratos
de
dados
[aula:
TAD]
• Procurar
dar
independência
aos
módulos,
para
que
possam
eventualmente
ser
reaproveitados
Modularização
Modularização
Modularização
Modularização
Atenção: incluir timer.h e
timer.c no projeto
Modularização
transformação
em
biblioteca
)mer.lib
Copiar timer.h para o diretório
“includes” do compilador
Copiar timer.lib para o diretório
lib do compilador
Constantes
e
#define
• Não
usar
“números
mágicos”
no
código
• Algumas
constantes
usadas
no
programa
podem
ter
que
ser
modificadas,
e
é
mais
fácil
fazer
isso
em
um
lugar
só
• Sempre
que
for
tornar
o
código
mais
legível,
usar
#define
para
dar
um
nome
à
constante
– Em
geral,
nomes
de
constantes
são
em
maiúsculas
#define PI 3.141592
#define MAX_VETOR 1000
Nomes
de
variáveis
• Algumas
variáveis
merecem
nomes
significa)vos:
MAX_VETOR, numClientes, listaAlunos
• Variáveis
auxiliares
em
geral
recebem
nomes
curtos:
i, j, aux, x
– Cuidado
para
não
fazer
confusão
– Não
abusar: i, ii, iii, aux1, aux2,
aux3...
– Variáveis
inteiras:
i, j, k
– Variáveis
reais:
x, y, z
– Strings:
s1, s2
– Booleanas:
nome
do
teste
(existe, valido,
ocorre)
Nomes
de
variáveis
• Es)los
variados:
– Só
minúsculas
(i, num, conta)
– Só
maiúsculas
(constantes:
PI, E, MAX)
– CamelCase
(numMat, anguloEntrada)
– Indicação
do
)po
no
início
do
nome
(iNum,
iValor, fRaio, fAltura, dVolume)
• Há
quem
prefira
inserir
comentários
e
usar
nomes
de
variáveis
em
inglês,
por
ficar
mais
próximo
da
linguagem
de
programação
Organização
e
limpeza
•
Procurar
dar
um
aspecto
organizado
ao
código,
ajuda
na
compreensão
• Entender
o
código
fonte
como
um
instrumento
de
comunicação
• Comentar
excessivamente
código
mal
escrito
não
ajuda
• Dar
nomes
adequados
a
variáveis
ajuda
bastante
Parênteses
e
espaçamento
• Usar
espaços
antes
de
parênteses,
depois
de
vírgulas,
ao
redor
de
operadores
binários
if (x == 10) y = 5;
for (i = 0; i < 10; i++) {
x += a;
a = f(b);
}
• Cuidado
com
notações
compactas
demais,
e
com
comandos
embu)dos
em
outros
if (x++ == b) y = 5;
Correção
e
robustez
• Testes:
prever
todo
)po
de
problema
e
variações
na
entrada
de
dados
– Limites
de
vetores
– Valores
inteiros
e
de
ponto
flutuante
– Contadores
e
incremento
– Testes
de
fim
de
arquivo
– Teste
de
disponibilidade
de
memória
para
alocação
Compilação
• LER
as
mensagens
de
erro
e
ENTENDER
a
origem
do
problema
• Warnings:
indicam
problemas
potenciais,
devem
ser
resolvidos
• Muitas
vezes
a
mensagem
de
erro
não
reflete
o
que
está
ocorrendo
– Observar
a
linha
em
que
o
erro
foi
indicado,
a
linha
anterior,
o
bloco
de
código
em
que
ocorreu,
e
o
corpo
da
função
em
que
ocorreu
Debugger
• Ajuda
a
acompanhar
os
valores
das
variáveis
ao
longo
da
execução
– Observar
o
valor
de
variáveis
(watches)
– Posicionar
pontos
de
interrupção
(breakpoints)
– Executar
passo
a
passo
• Vide
http://wiki.codeblocks.org/index.php?title=Debugging_with_Code::Blocks
• Documentação
do
CodeBlocks
http://wiki.codeblocks.org/index.php?title=Main_Page
AEDSII_aula_002_linguagem_C-entrada_e_saida.pdf
ENTRADA
E
SAÍDA
Obje%vos
• Entrada
e
saída
formatada
• Uso
de
arquivos
• Escrita
e
leitura
de
blocos
de
dados
• Movimentação
em
arquivos
I/O
em
C
• Formalmente,
ro%nas
de
entrada
e
saída
não
fazem
parte
da
linguagem,
e
sim
de
bibliotecas
que
acompanham
os
compiladores
– Felizmente,
são
padronizadas
– Exige-‐se
a
linha
#include
<stdio.h>
para
usá-‐las
I/O
em
C
• int printf(const char *format, ...);
– Retorna
o
número
de
caracteres
impressos
– O
string
contém
uma
“máscara”
(template)
com
lacunas
reservadas
para
os
valores
que
serão
impressos
– Pode
não
exis%r
lacuna
printf(“O valor de x eh %d”, x);
printf(“Area: %f\n”, PI*d*d/4);
printf(“Nome: %s”, nomeAluno);
prinT
• Especificadores
de
formato
– %c
(char)
– %s
(string)
– %d
(int)
– %ld
(long
int)
– %f
(float)
– %lf
(double)
– %e
(float
notação
cienXfica)
– %g
(e
ou
f,
ou
seja,
notação
cienXfica
se
necessário)
prinT
• %[flags][width][.precision][length]specifier
Caracteres
de
escape
• Acrescentados
à
máscara
para
provocar
reposicionamento
do
cursor
– \n:
nova
linha
– \t:
tabulação
– \r:
backspace
– \\:
caractere
da
barra
inver%da
prinT
int main() {
int ret;
ret = printf("Hello world!\n");
printf("ret: %d\n", ret);
printf("%p %p\n", &ret, (int *) ret);
return 0;
}
Entrada
• Com
máscara:
scanf(string,
*var
[,
*var,
...]);
– Mesmos
especificadores
de
formato
do
prinT
– A
função
precisa
receber
o
endereço
da
variável
à
qual
o
valor
digitado
será
atribuído
scanf(“%d”, &num)
scanf(“%c%d”, &letra, &num);
scanf(“%c”, &ch);
scanf(“%s”, s); // string
scanf(“%13c”, s); //le 13 caracteres
scanf(“ %c”, &ch); //pula brancos
Entrada
Entrada
• Observe
que
scanf
interrompe
a
leitura
de
um
string
quando
encontra
um
branco,
se
usado
com
%s
• Uso
de
%[]:
– %[aeiou]:
apenas
as
vogais
são
permi%das
– %[^aeiou]:
as
vogais
não
são
permi%das
– %[^\n]:
interrompe
quando
recebe
um
[enter]
– %60[^\n]:
admite
até
60
caracteres,
e
para
quando
encontra
um
enter
Entrada
• Linhas
inteiras:
char *gets(char *);
– Lê
uma
linha
inteira,
excluindo
\n,
e
coloca
\0
no
final
– Com
limite
de
tamanho:
• fgets(string, tamMax, stdin)
Entrada
int main() {
char str[10];
char str2[10];
char str3[10];
gets(str);
gets(str2);
fgets(str3, 10, stdin);
printf("str: %s\nstr2: %s\nstr3: %s", str, str2,str3);
return 0;
}
Entrada
• Caracteres
individuais:
int getchar(void);
– O
caractere
digitado
é
o
valor
de
retorno
da
função
ret = getchar();
printf("entrada: %c %d\n", ret, ret);
> 1
> entrada: 1 49
Exemplo (POSCOMP 2009)
#include<stdio.h>
#include<string.h>
int main (void)
{
char texto[]= "foi muito facil";
int i;
for (i = 0; i < strlen(texto); i++){
if (texto[i] == ' ') break;
}
i++;
for ( ; i < strlen(texto); i++)
printf("%c", texto[i]);
return 0;
}
O que será impresso quando
o programa for executado?
I/O
para
arquivos
• A
entrada
do
teclado
e
saída
para
o
monitor
são
realizadas
internamente
considerando
três
disposi%vos
virtuais:
stdin,
stdout
e
stderr
– Como
são
disposi%vos
padrão,
referências
a
stdin
e
stdout
eles
são
omi%das
dos
comandos
– fgets(string, tamMax, stdin);
• I/O
para
arquivos
é
muito
semelhante
à
operação
com
stdin
e
stdout,
mas
um
handle
ao
arquivo
tem
que
ser
fornecido
I/O
para
arquivos
// abre ou cria um arquivo
// retorno: handle para arquivo criado
FILE *fopen(const char *name, const char *type);
// fecha um arquivo
// retorna 0 se executado com sucesso
int fclose(FILE *);
// remove dados do buffer e envia para o arquivo
// retorna 0 se executado com sucesso
int fflush(FILE *);
// testa final de arquivo
// Retorna diferente de zero se fim do arquivo
foi atingido
int feof(FILE *);
I/O
para
arquivos
• fopen:
modos
de
abertura
I/O
para
arquivos
• O
handle
é
ob%do
no
momento
da
abertura
do
arquivo
FILE *inFile; // variável handle
FILE *outfile;
...
//abre o arquivo para leitura (r) ou gravacao (w)
inFile = fopen(“arquivo.txt”, “r”);
outFile = fopen(“saida.txt”, “w”);
...
fscanf(inFile, “%d”, &num);
...
fprintf(outFile, “O valor lido eh %8.2d\n”, num);
...
fclose(inFile);
fclose(outFile);
I/O
para
arquivos
• Se
o
handle
retornar
nulo
do
comando
fopen,
então
ocorreu
erro
(arquivo
não
encontrado,
arquivo
travado
contra
gravação,
permissão
negada
pelo
sistema
operacional,
etc.)
• Testar:
if ((inFile = fopen(“arquivo.txt”, “r”)) == NULL)
{
printf(“Nao consegui abrir.\n”);
exit(1);
}
I/O
para
arquivos
• Equivalências
• gets()
à
fgets(arq,
tamMax,
string);
• getchar()
à
fgetc(arq);
• putc(ch)
à
fputc(arq,
ch)
• prinT
à
fprinT(arq,
string,
valor)
• scanf
à
fscanf(arq,
string,
endereço)
I/O
para
arquivos
#include <stdio.h>
#include <stdlib.h>
int main() {
FILE *f;
char ch;
f = fopen("main.c","r");
while ((ch = fgetc(f)) != EOF)
printf("%c", ch);
fclose(f);
return 0;
}
I/O
para
arquivos
(variação)
#include <stdio.h>
#include <stdlib.h>
int main() {
FILE *f;
char ch;
f = fopen("main.c","r");
while (!feof(f)) {
ch = fgetc(f);
printf("%c", ch);
}
fclose(f);
return 0;
}
I/O
para
arquivos
• Movimentação
em
arquivos
// retorna a posição atual do arquivo
long ftell(FILE *f);
// seta posição no arquivo, com relação à variável origin
// retorna 0 se bem sucedido (offset em bytes).
int fseek(FILE *f, long offset, int origin);
origin
Macro Valor deslocamento relativo
SEEK_SET 0 Início do arquivo
SEEK_CUR 1 Posição atual
SEEK_END 2 Fim do arquivo
int main() {
FILE *f;
char arquivo[] = "main.c";
long int pos;
char str[512];
f = fopen(arquivo,"r");
pos = ftell(f);
fgets(str, 512, f);
printf("[posicao: %ld]
%s\n", pos, str);
fseek(f, 10, SEEK_SET);
pos = ftell(f);
fgets(str, 512, f);
printf("[posicao: %ld]
%s\n", pos, str);
I/O
para
arquivos
fseek(f, -15, SEEK_END);
pos = ftell(f);
fgets(str, 512, f);
printf("[posicao: %ld] %s\n",
pos, str);
fclose(f);
return 0;
}
Numerando
linhas
int main() {
FILE *f;
char ch;
int nlinha = 1;
f = fopen("main.c","r");
printf("%d: ", nlinha++);
while (!feof(f)) {
ch = fgetc(f);
printf("%c", ch);
if (ch == '\n')
printf("%d: ", nlinha++);
}
fclose(f);
return 0;
}
Entrada
da
Linha
de
Comando
• Comunicação
pela
linha
de
comando
int main(int argc, char *arg[]) {
int i, vezes;
vezes = atoi(argv[2]);
for (i = 0; i < vezes; i++)
printf(“%s\n”, argv[1]);
return 0;
}
./exec teste 10
I/O
para
arquivos
• Leitura
e
escrita
de
blocos
de
dados
// lê n objetos com tamanho de size bytes cada
// retorno: número de objetos lidos
size_t fread(void *ptr, size_t size, size_t n, FIE *f);
// escreve n objetos com tamanho de siz bytes cada
// retorno: número de objetos escritos
size_t fwrite(void *ptr, size_t size, size_t n, FILE *f);
#include <stdlib.h>
#include <stdio.h>
typedef struct {
string nome;
int matricula;
char conceito;
} TipoAluno;
main() {
TipoAluno al;
al.nome = “Pedro”
al.matricula = 200712;
al.conceito = ‘A’;
}
I/O
para
arquivos
main() {
TipoAluno al;
FILE *f;
int c;
al.nome = “Pedro”
al.matricula = 200712;
al.conceito = ‘A’;
f = fopen(“arquivo.dat”, “w”);
c = fwrite(&al,
sizeof(TipoAluno), 1, f);
fclose(f);
}
I/O
para
arquivos
• Outras
funções
úteis
// cria um arquivo temporário (removido quando fechado)
// retorno: handle para arquivo criado
FILE *tmpfile(void);
// gera um nome único que pode ser usado com nome de
arquivo
char *tmpnam(char *);
Exercícios
1. Reescreva
o
programa
para
numerar
linhas
u%lizando
a
função
fgets().
2. Crie
um
programa
para
contar
o
número
de
ocorrências
de
cada
caractere
con%do
em
um
arquivo.
Imprima
uma
tabela
mostrando
o
número
de
ocorrências.
3. Implemente
um
programa
para
contar
o
número
de
linhas
em
um
arquivo.
Exercícios
3. Crie
um
programa
que
salve
os
dados
a
seguir
em
arquivo.
typedef struct {
string nome;
int matricula;
char conceito;
} TipoAluno;
int main(){
TipoAluno alunos[75];
...
4. Crie
um
programa
para
ler
apenas
os
registros
ímpares,
salvos
pelo
código
do
exercício
3.
Exercício 1
char arquivo[] = "main.c";
FILE *f;
int ocorrencias[256];
int valor, i;
memset(ocorrencias, 0, 256 * sizeof(int));
f = fopen(arquivo, "r");
while (!feof(f)) {
valor = fgetc(f);
ocorrencias[valor]++;
}
for (i = 0; i < 256; i++) {
printf("%d [%c]: %d\n", i, i, ocorrencias[i]);
}
fclose(f);
Exercício 2
char arquivo[] = "main.c";
char str[1024];
FILE *f;
int nlinhas = 0;
f = fopen(arquivo, "r");
while (!feof(f)) {
fgets(str, 1024, f);
nlinhas++;
}
printf("numero de linhas: %d\n", nlinhas);
fclose(f);
return 0;
AEDSII_aula_003_linguagem_C-TAD.pdf
The image cannot be displayed. Your computer may not have
enough memory to open the image, or the image may have
been corrupted. Restart your computer, and then open the file
again. If the red x still appears, you may have to delete the
image and then insert it again.
The image
cannot be
displayed.
Your
computer
may not
have
enough
memory to
open the
image, or
the image
may have
Tipos Abstratos de Dados
Luiz Chaimowicz, Raquel O. Prates e
Gisele L. Pappa
(versão adaptada)
Livro “Projeto de Algoritmos”
Capítulo 1
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
n Algoritmo e Programa
n Tipo Abstrato de Dados
q Qual papel do programador e do usuário do TAD
n Conceitos de typedef e struct
Algoritmos e Estrutura de Dados II
3 Pontos Principais
© R. O. Prates,
L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Qual a diferença entre um
algoritmo e um programa?
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmo ou Programa?
Algoritmos e Estrutura de Dados II
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmo ou Programa?
Algoritmos e Estrutura de Dados II
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Algoritmos e Estruturas de Dados
n Algoritmo:
q Sequência de ações executáveis para a
solução de um determinado tipo de problema
q Exemplo: “Receita de Bolo”
q Algoritmos trabalham sobre Estruturas de Dados
n Estrutura de Dados:
q Conjunto de dados que representa uma situação
real (estado do mundo)
q Modo eficiente de armazenamento para facilitar seu
acesso e modificação.
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Representação dos Dados
n Os dados podem estar representados
(estruturados) de diferentes maneiras
n Normalmente, a escolha da representação
é
determinada pelas operações que serão
utilizadas sobre eles
n Exemplo: números inteiros q Representação por palitinhos: II + IIII = IIIIII
q Representação decimal: 1278 + 321 = 1599
q Boa para pequenos números (operação simples)
q Boa para números maiores (operação complexa)
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Programas
n Um programa é uma formulação concreta
de um algoritmo abstrato, baseado em
representações de dados específicas
n Os programas são feitos em alguma
linguagem que pode ser entendida e seguida
pelo computador
q Linguagem de máquina
q Linguagem de alto nível (uso de compilador)
q Aqui vamos utilizar a Linguagem C
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Linguagem C
n Criada em no início da década de 70 para
a
programação do sistema operacional Unix
n Uma das linguagens mais utilizadas no
mundo, e serviu como base para outras
como C++, C#, etc.
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Tipos Abstratos de Dados (TADs)
n Agrupa a estrutura de dados juntamente com
as operações que podem ser feitas sobre
esses dados
n O TAD encapsula a estrutura de dados. Os
usuários do TAD só tem acesso a algumas
operações disponibilizadas sobre esses dados
n Usuário do TAD x Programador do TAD
q Usuário só “enxerga” a interface, não a
implementação
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Tipos Abstratos de Dados (TADs)
n Dessa forma, o usuário pode abstrair da
implementação específica.
n Qualquer modificação nessa implementação
fica restrita ao TAD
n A escolha de uma representação específica é
fortemente influenciada pelas operações a
serem executadas
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Tipos Abstratos de Dados (TADs)
Algoritmos e Estrutura de Dados II
Aplicação
Especificação
Implementação
Usuário do TAD
Programador do TAD
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Exemplo: Lista de números inteiros
n Operações
q Faz Lista Vazia
q Insere número no começo da lista
q Remove de uma posição i
20 13 02 30 Implementação por Vetores:
void Insere(int x, Lista L) {
for(i=0;...) {...}
L[0] = x;
}
20 13 02 30
Implementação por Listas Encadeadas
void Insere(int x, Lista L) {
p = CriaNovaCelula(x);
L.primeiro = p;
...
}
Programa usuário do TAD:
int main() {
Lista L;
int x;
x = 20;
FazListaVazia(L);
Insere(x,L);
...
}
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Implementação de TADs
n Em linguagens orientadas por objeto (C++, Java) a
implementação é feita através de classes
n Em linguagens estruturadas (C, pascal) a
implementação é feita pela definição de tipos
juntamente com a implementação de funções
n Vamos utilizar os conceitos em C (typedef e struct)
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted.
Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Estruturas (Structs) em C
n Uma estrutura é uma coleção de uma ou mais
variáveis, possivelmente de tipos diferentes,
colocadas juntas sob um único nome para
manipulação conveniente
n Exemplo:
q para representar um aluno são necessárias as informações
nome, matrícula, conceito
q Ao invés de criar três variáveis, é possível criar uma única
variável contendo três campos.
n Em C, usa-se a construção struct para representar
esse tipo de dado
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Estruturas (Structs) em C
n Sintaxe:
struct nome {
[tipo nome_da_variável] ;
...
} [variável] ;
struct Aluno {
string nome;
int matricula;
char conceito;
};
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Estruturas (Structs) em C
#include<iostream>
#include<string>
struct Aluno {
string nome;
int matricula;
char conceito;
};
main() {
struct Aluno al, aux;
al.nome = “Pedro”
al.matricula = 200712;
al.conceito = ‘A’;
aux = al;
}
Pedro
200712 A
al:
Pedro
200712 A aux:
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Estruturas (Structs) em C
struct Aluno {
string nome;
int matricula;
char conceito;
};
struct Professor{
string nome;
int matricula;
string classes[3];
};
main() {
struct Aluno al;
struct Professor pr;
al.nome = “Pedro”;
pr.nome = “José”;
}
main() {
string alunoNome;
int alunoMatricula;
Char alunoConceito;
string alunoNome2;
int alunoMatricula2;
Char alunoConceito2;
string professorNome;
int professorMatricula;
string professoClasses[3];
alunoNome = “Pedro”
alunoMatricula = 200712;
alunoConceito = ‘A’;
alunoNome2 = alunoNome;
alunoMatricula2 = alunoMatricula;
alunoConceito2 = alunoConceito;
}
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Declaração de Tipos
n Para simplificar, uma estrutura ou mesmo
outros tipos de dados podem ser definidos
como um novo tipo
n Uso da construção typedef
n Sintaxe: typedef tipo identificador;
typedef struct {
string nome;
int matricula;
char conceito;
} TipoAluno;
typedef int Vetor[10];
int main() {
TipoAluno al;
Vetor v;
...
}
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
TADs em C
n Para implementar um Tipo Abstrato de
Dados em C, usa-se a definição de tipos
juntamente com a implementação de funções
que agem sobre aquele tipo
n Como boa regra de programação, evita-se
acessar o dado diretamente, fazendo o
acesso só através das funções
q Mas, diferentemente de C++ e Java, não há uma
forma de proibir o acesso.
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
n Uma boa técnica de programação é
implementar os TADs em arquivos separados
do programa principal
n Para isso geralmente separa-se a declaração
e a implementação do TAD em dois arquivos:
q NomeDoTAD.h : com a declaração
q NomeDoTAD.c : com a implementação
n O programa ou outros TADs que utilizam o
seu TAD devem dar um #include no arquivo .h
TADs em C
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
TADs em C
Algoritmos e Estrutura de Dados II
Aplicação
Especificação
Implementação
Usuário do TAD
Programador do TAD
arquivo .c
arquivo .h
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Exemplo
n Implemente um TAD ContaBancaria, com os
campos número e saldo onde os clientes
podem fazer as seguintes operações:
q Iniciar uma conta com um número e saldo inicial
q Depositar um valor
q Sacar um valor
q Imprimir o saldo
n Faça um pequeno programa para testar o
seu TAD
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
ContaBancaria.h
// definição do tipo
typedef struct {
int numero;
double saldo;
} ContaBancaria;
// cabeçalho das funções
ContaBancaria Inicializa (int, double);
void Deposito (ContaBancaria *, double);
void Saque (ContaBancaria *, double);
void Imprime (ContaBancaria);
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
ContaBancaria.c
#include<stdio.h>
#include"Contabancaria.h"
ContaBancaria Inicializa(int numero, double saldo) {
ContaBancaria conta;
conta.numero = numero;
conta.saldo = saldo;
return conta;
}
void Deposito (ContaBancaria *conta, double valor) {
conta->saldo += valor;
}
void Saque (ContaBancaria *conta, double valor) {
conta->saldo -= valor;
}
void Imprime (ContaBancaria conta) {
printf("Numero: %d – saldo: %f\n", conta.numero, conta.saldo);
}
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Main.c
#include<stdio.h> #include<stdlib.h>
#include "ContaBancaria.h"
int main (void) {
ContaBancaria conta1;
conta1 = Inicializa(918556, 300.00);
printf("\nAntes da movimentacao:\n ");
Imprime(conta1);
Deposito(&conta1, 50.00);
Saque(&conta1, 70.00);
printf("\nDepois da movimentacao:\n ");
Imprime(conta1);
return(0);
}
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
TADs em C
Algoritmos e Estrutura de Dados II
Aplicação
Especificação
Implementação
Usuário do TAD
Programador do TAD
ContaBancaria.c
ContaBancaria.h
main.c
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
TADs em C
n Acesso direto dos dados (errado!)
Algoritmos e Estrutura de Dados II
20 13 02 30 Implementação por Vetores:
typedef struct {
int dado[100];
} Lista;
20 13 02 30
Implementação por Listas Encadeadas
typedef struct item {
int dado;
struct item *prox;
} Item;
typedef struct {
Item *inicio;
} Lista;
Programa usuário do TAD:
int main() {
Lista L;
L.dado[0] = 20;
}
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Exercício
n Implemente um TAD Número Complexo
q cada número possui os campos real e imaginário
q Implemente as operações:
q Inicializa: atribui valores para os campos
q Imprime: imprime o número da forma “R + Ci”
q Copia: Copia o valor de um número para outro
q Soma: Soma dois números complexos
q EhReal: testa se um número é real
n Faça um pequeno programa para testar o
seu TAD
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
NumeroComplexo.h
typedef struct {
int real;
int img;
} NumeroComplexo ;
NumeroComplexo Inicializa(int, int);
void Imprime(NumeroComplexo);
void Copia(NumeroComplexo*, NumeroComplexo);
NumeroComplexo Soma(NumeroComplexo, NumeroComplexo);
int EhReal(NumeroComplexo);
!
!
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
NumeroComplexo.c
#include <stdio.h>
#include "NumeroComplexo.h"
NumeroComplexo Inicializa(int real, int img) {
NumeroComplexo num;
num.real = real;
num.img = img;
return num;
}
void Imprime(NumeroComplexo num) {
printf("%d + %di\n", num.real, num.img);
}
!
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
NumeroComplexo.cpp
NumeroComplexo Soma(NumeroComplexo a, NumeroComplexo b) {
NumeroComplexo temp;
temp.real = a.real + b.real;
temp.img = a.img + b.img;
return temp;
}
int EhReal(NumeroComplexo num) {
return num.img == 0;
}
void Copia(NumeroComplexo *dest, NumeroComplexo src)
{
dest->real = src.real;
dest->img = src.img;
}
!
© R. O. Prates, L. Chaimowicz e
Gisele L. Pappa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
#include <stdio.h>
#include <stdlib.h>
#include "NumeroComplexo.h"
int main() {
NumeroComplexo a,b,c,d;
a = Inicializa(2,5);
Imprime(a);
b = Inicializa(1,2);
Imprime(b);
c = Soma(a,b);
Imprime(c);
d = Inicializa(5,0);
Imprime(d);
if (EhReal(d))
Copia(&d,a);
Imprime(d);
return 0;
}!
AEDSII_aula_004_linguagem_C-vetores_e_strings.pdf
VETORES
E
STRINGS
Alocação
está-ca
de
memória
• Ao
se
declarar
uma
variável
qualquer,
o
compilador
deixa
reservado
um
espaço
suficiente
na
memória
para
armazená-‐la
int a; // 4 bytes
float x; // 4 bytes
double y; // 8 bytes
char c; // 1 byte
char *c; // 4 bytes
Alocação
está-ca
de
memória
• Ao
fazer
a
alocação
está-ca,
apenas
o
espaço
necessário
na
memória
é
reservado
• O
conteúdo
de
cada
posição
não
é
alterado,
e
portanto
uma
variável
apenas
declarada
pode
conter
qualquer
coisa
• Inicializar
as
variáveis,
atribuindo
valores,
antes
do
uso
– Inclusive
vetores,
matrizes
e
strings
Vetores
• Quando
se
declara
um
vetor,
o
valor
entre
colchetes
indica
quantas
vezes
o
espaço
de
memória
necessário
para
o
-po
básico
será
alocado
char v[100]; // 100 * sizeof(char) = 100 bytes
int v[100]; // 100 * sizeof(int) = 400 bytes
float vf[200]; // 200 * sizeof(float) = 800 bytes
double z[1000]; // 1000 * sizeof(double) = 8000 bytes
Pode-‐se
u-lizar:
sizeof(v)
Pode
ser
u-lizado
para
descobrir
o
tamanho
de
uma
string?
Vetores
• A
referência
a
uma
posição
de
um
vetor
indica
o
cálculo
de
uma
posição
de
memória
a
par-r
do
início
do
vetor
float x[1000];
// x[20] está na posição x + 20*sizeof(float)
• Na
verdade,
o
símbolo
x
é
um
apontador
para
o
início
da
região
de
memória
reservada
para
o
vetor
Vetores
• C
NÃO
AVISA
NEM
PRODUZ
ERRO
QUANDO
O
LIMITE
DE
UM
VETOR
OU
MATRIZ
FOR
EXCEDIDO
float x[1000];
y = x[2000]; // não dá erro, mas vai acessar
// uma parte inesperada da memória
– Erro
mais
comum
(run-me):
segmentation fault
• É
responsabilidade
do
programador
verificar
os
limites,
e
garan-r
que
não
sejam
excedidos
Matrizes
=
Vetores
de
mais
de
uma
dimensão
• Na
verdade,
a
alocação
na
memória
é
linear
• Muda
apenas
o
cálculo
da
posição
de
memória
do
elemento
referenciado
int M[5][5];
...
M[0][0] = 15;
M[2][3] = 2; // posicao: M + (2*5 + 3)*sizeof(int)
Matrizes
a b c d e f g h i j k l m n o
char M[3][5];
v = M[1][4];
M
a b c d e
f g h i j
k l m n o
M[1][4]
M[1][4]
char *M;
M = (char *) malloc(3 * 5 * sizeof(char));
// acesso a linha i e coluna j em matriz l x c
// v = M[i * c + j]
v = M[1 * 5 + 4];
Strings
• Um
string
é
um
vetor
do
-po
char
• Para
manipulação
do
string,
atribuindo
e
recuperando
valores,
e
realizando
operações
sobre
ele
(funções
no
string.h),
é
importante
entender
essa
caracterís-ca
• Quando
o
conteúdo
de
um
string
não
ocupa
todo
o
espaço
disponível,
usa-‐se
um
caractere
‘\0’
(ou
NULL,
código
ASCII
0)
como
delimitador
Strings
• Strings
constantes
aparecem
no
código
entre
aspas
printf(“%s”, “Bom dia!”);
• O
delimitador
\0
está
incluído:
• Tamanho
da
string:
size_t strlen(char *str);
Strings
• Não
é
possível
fazer
atribuições
diretas
para
strings
• Usar
a
função
strcpy
ou
a
função
strncpy
char *strcpy(char *DST, char *SRC);
Strings
• Tamanho
da
string
(não
conta
o
\0):
size_t strlen(char *str);
char s[10];
int tamanho;
strcpy(s, “Bom dia!\n”);
tamanho = strlen(s); // 9
tamanho = sizeof(s); // 10 (Não usar!)
Strings
• Na
inicialização,
pode-‐se
usar
o
mesmo
recurso
disponível
para
vetores
• char nome[] = {‘A’, ‘n’, ‘a’, ‘\0’};
Ou
• char nome[] = “Ana”;
Strings
• Como
o
nome
do
string
representa
o
endereço
onde
começa
o
string,
é
possível
manipulá-‐lo
diretamente
– Cuidado!
• Exemplo
char nome[] = “Alexandre”;
printf(“%s\n”, nome + 3); // imprime “xandre”
Strings
• Funções
– strcat(s1,
s2):
concatena
o
s2
no
s1
(s1
tem
que
ter
espaço)
– strcmp(s1,
s2):
retorna
– <
0
se
s1
é
menor
que
s2,
– 0
se
s1
é
igual
a
s2
– >
0
se
s1
é
maior
que
s2
(ordem
alfabé-ca)
• A
comparação
entre
strings
também
tem
que
ser
feita
caractere
a
caractere,
• Não
se
pode
usar
s1==s2;
isso
só
compara
os
endereços
Strings
• Comparação
de
strings
char str1[] = "abcd ";
char str2[] = "abcd ";
int cmp;
cmp = strcmp(str1, str2); // retorna 0
str2[4] = 'e';
str1[4] = 'a';
cmp = strcmp(str1, str2); // retorna -1
str2[4] = 0;
cmp = strcmp(str1, str2); // retorna 1
Strings
• Impressão
para
uma
string
(sprinj)
char str1[10];
sprintf(str1, “%d“, 33);
Strings
• strncat,
strncmp,
strncpy:
idem
aos
anteriores,
mas
especifica
o
número
de
caracteres
que
serão
considerados
Strings
• strtok:
extrai
“tokens”,
substrings
delimitados
char *strtok(char *str, char *delim);
Exemplo:
str = “algumas palavras”;
delim = “ \n”;
token = strtok(str, delim);
printf(“%s\n”, token); // stdout: algumas
token = strtok(NULL, delim);
printf(“%s\n”, token); // stdout: palavras
// memória: str: algumas\0palavras\0
Strings
• Exemplo
int num = 0; char linha[256];
...
while (!feof(infile)) {
fgets(linha, 256, infile);
p1 = strtok(linha, " \n"); //delim: branco ou fim de linha
while ((p1 != NULL) && (!feof(infile)))
{
num++;
printf("%s\n", p1);
p1 = strtok(NULL, " \n");
}
}
Strings
• Vetores
de
strings
podem
ser
criados
• Exemplo
char DiaSemana[7][14] = {“Domingo”,
“Segunda”, “Terça”, “Quarta”,
“Quinta”, “Sexta”, “Sabado”};
...
printf(“%s\n”, DiaSemana[3]);
Algoritmos
e
Estrutura
de
Dados
II
Passagem
de
Parâmetros
• Em
C++,
parâmetros
para
função
podem
ser
passados
por
valor
ou
por
referência
– Por
valor:
o
parâmetro
formal
(recebido
no
procedimento)
é
uma
cópia
do
parâmetro
real
(passado
na
chamada)
– Por
referência:
o
parâmetro
formal
(recebido
no
procedimento)
é
uma
referência
para
o
parâmetro
real
(passado
na
chamada)
• As
modificações
efetuadas
acontecem
no
parâmetro
real
• Em
C
só
existe
passagem
por
valor,
logo
deve-‐se
implementar
a
passagem
por
referência
u-lizando-‐se
apontadores
Algoritmos
e
Estrutura
de
Dados
II
Passagem
de
Parâmetros
(C)
void SomaUm(int x, int *y)
{
x = x + 1;
*y = (*y) + 1;
printf("Funcao SomaUm: %d %d\n", x, *y);
}
int main()
{
int a=0, b=0;
SomaUm(a, &b);
printf("Programa principal: %d %d\n", a,
b);
}
1 1
0 1
Passagem
de
parâmetros
para
o
programa
• Chamada:
C:\> prog.exe arg1 arg2 arg3
• Declaração
completa
da
função
main
int main(int argc, char *argv[])
• argc:
número
de
parâmetros
passados
na
linha
de
comando
• argv:
um
vetor
de
argc
strings
– argv[0]:
nome
do
programa
– argv[1]:
primeiro
parâmetro
– argv[argc
–
1]:
úl-mo
parâmetro
– argv[argc]
é
sempre
NULL
AEDSII_aula_005_analise_de_complexidade.pdf
Medida do Tempo de
Execução de um Programa
Livro “Projeto de Algoritmos” – Nívio Ziviani
Capítulo 1 – Seção 1.3
http://www2.dcc.ufmg.br/livros/algoritmos/
Algoritmos e Estrutura de Dados II
Projeto de Algoritmos
n Projeto de algoritmos
1. Análise do problema
2. Decisões de projeto
3. Algoritmo a ser utilizado de acordo com seu
comportamento.
n Comportamento depende de
n tempo de execução
n espaço ocupado.
Algoritmos e Estrutura de Dados II
Análise de Algoritmos
n Análise de um algoritmo particular.
q Qual é o custo de usar um dado algoritmo para resolver um
problema específico?
Algoritmos e Estrutura de Dados II
Tipos de Problemas na
Análise de Algoritmos
n Análise de um algoritmo particular.
q Qual é o custo de usar um dado algoritmo
para resolver um problema específico?
q Características que devem ser investigadas:
q Análise do número de vezes que cada parte
do algoritmo deve ser executada,
q Estudo da quantidade de memória
necessária.
Algoritmos e Estrutura de Dados II
Tipos de Problemas na
Análise de Algoritmos
n Análise de uma classe de algoritmos.
q Qual é o algoritmo de menor custo possível
para resolver um problema particular?
q Toda uma família de algoritmos é investigada.
q Procura-se identificar um que seja o melhor
possível.
q Coloca-se limites para a complexidade
computacional dos algoritmos pertencentes à
classe.
Algoritmos e Estrutura de Dados II
Custo de um Algoritmo
n Determinando o menor custo possível para resolver
problemas de uma dada classe, temos a medida da
dificuldade inerente para resolver o problema.
n Quando o custo de um algoritmo é igual ao menor custo
possível, o algoritmo é ótimo para a medida de custo
considerada.
n Podem existir vários algoritmos para resolver o mesmo
problema.
n Se a mesma medida de custo é aplicada a diferentes
algoritmos, então é possível compará-los e escolher o
mais adequado.
Algoritmos e Estrutura de Dados II
Medida do Custo pela Execução do Programa
n Medidas são bastante inadequadas :
q os resultados são dependentes do compilador;
q os resultados dependem do hardware;
q quando grandes quantidades de memória são utilizadas, as
medidas de tempo podem depender deste aspecto.
n Apesar disso, há argumentos a favor de se obterem medidas
reais de tempo.
q Ex.: quando há vários algoritmos distintos para resolver um
mesmo tipo de problema, todos com um custo de execução
dentro de uma mesma ordem de grandeza.
q Nesse caso, tanto os custos reais das operações como os custos
não aparentes, tais como alocação de memória, indexação,
carga, são considerados.
Algoritmos e Estrutura de Dados II
Medida do Custo por meio
de um Modelo Matemático
n Usa um modelo matemático baseado em um
computador idealizado.
n Deve ser especificado o conjunto de operações e seus
custos de execuções.
n É mais usual ignorar o custo de algumas das operações e
considerar apenas as operações mais significativas.
n Ex.: algoritmos de ordenação. Consideramos o
número de comparações entre os elementos do conjunto
a ser ordenado e ignoramos as operações aritméticas,
de atribuição e manipulações de índices, caso existam.
Algoritmos e Estrutura de Dados II
Função de Complexidade
n O custo de execução de um algoritmo é dado por
função de custo ou função de complexidade f.
n f(n) é a medida do tempo necessário para executar
um algoritmo para um problema de tamanho n.
n Função de complexidade de tempo:
n f(n) mede o tempo necessário para executar um
algoritmo em um problema de tamanho n.
n Função de complexidade de espaço
n f(n) mede a memória necessária para executar
um algoritmo em um problema de tamanho n.
Algoritmos e Estrutura de Dados II
Função de Complexidade
n Nas aulas, f denota uma função de complexidade
de tempo
n Apesar do nome, ela não representa tempo
diretamente
n Representa o número de vezes que
determinada operação considerada relevante
é executada.
Algoritmos e Estrutura de Dados II
Exemplo: maior elemento
n Considere o algoritmo para encontrar o maior elemento de um
vetor de inteiros A[n]; n ≥ 1.
n Seja f uma função de complexidade tal que f(n) é o número de
comparações entre os elementos de A, se A contiver n
elementos.
n Qual a função f(n)?
int Max(int A[n]) {
int i, Temp;
Temp = A[0];
for (i = 1; i < n; i++)
if (Temp < A[i])
Temp = A[i];
return Temp;
}
Algoritmos e Estrutura de Dados II
Exemplo: maior elemento
n Considere o algoritmo para encontrar o maior elemento de um
vetor de inteiros A[n]; n ≥ 1.
n Seja f uma função de complexidade tal que f(n) é o número de
comparações entre os elementos de A, se A contiver n
elementos.
n Logo f(n) = n -1
int Max(int A[n]) {
int i, Temp;
Temp = A[0];
for (i = 1; i < n; i++)
if (Temp < A[i])
Temp = A[i];
return Temp;
}
Algoritmos e Estrutura de Dados II
Exemplo: maior elemento
n Teorema: Qualquer algoritmo para encontrar o maior
elemento de um conjunto com n elementos, n ≥ 1, faz
pelo menos n -1 comparações.
Algoritmos e Estrutura de Dados II
Exemplo: maior elemento
n Teorema: Qualquer algoritmo para encontrar o maior
elemento de um conjunto com n elementos, n ≥ 1, faz
pelo menos n -1 comparações.
n Prova: Cada um dos n - 1 elementos tem de ser
testado, por meio de comparações, se é menor do que
algum outro elemento.
Algoritmos e Estrutura de Dados II
Exemplo: maior elemento
n Teorema: Qualquer algoritmo para encontrar o maior
elemento de um conjunto com n elementos, n ≥ 1, faz
pelo menos n -1 comparações.
n Prova: Cada um dos n - 1 elementos tem de ser
testado, por meio de comparações, se é menor do que
algum outro elemento.
q Logo, n-1 comparações são necessárias
Algoritmos e Estrutura de Dados II
Exemplo: maior elemento
n Teorema: Qualquer algoritmo para encontrar o maior
elemento de um conjunto com n elementos, n ≥ 1, faz
pelo menos n -1 comparações.
n Prova: Cada um dos n - 1 elementos tem de ser
testado, por meio de comparações, se é menor do que
algum outro elemento.
q Logo, n-1 comparações são necessárias
O teorema acima nos diz que, se o número de
comparações for utilizado como medida de custo,
então a função Max do programa anterior é ótima.
Algoritmos e Estrutura de Dados II
Tamanho da Entrada de Dados
n A medida do custo de execução de um algoritmo
depende principalmente do tamanho da entrada
dos dados.
n Para alguns algoritmos, o custo de execução é
uma função da entrada particular dos dados, não
apenas do tamanho da entrada.
Algoritmos e Estrutura de Dados II
Tamanho da Entrada de Dados
n A medida do custo de execução de um algoritmo
depende principalmente do tamanho da entrada
dos dados.
n Para alguns algoritmos, o custo de execução é
uma função da entrada particular dos dados, não
apenas do tamanho da entrada.
n No caso da função Max do programa do exemplo, o
custo é uniforme sobre todos os problemas de tamanho
n.
n Para um algoritmo de ordenação isso não ocorre
Algoritmos e Estrutura de Dados II
Tamanho da Entrada de Dados
n A medida do custo de execução de um algoritmo
depende principalmente do tamanho da entrada
dos dados.
n Para
alguns algoritmos, o custo de execução é
uma função da entrada particular dos dados, não
apenas do tamanho da entrada.
n No caso da função Max do programa do exemplo, o
custo é uniforme sobre todos os problemas de tamanho
n.
n Para um algoritmo de ordenação isso não ocorre
n se os dados de entrada já estiverem quase ordenados,
então o algoritmo pode ter que trabalhar menos.
Algoritmos e Estrutura de Dados II
Melhor Caso, Pior Caso e Caso Médio
n Melhor caso: menor tempo de execução sobre
todas as entradas de tamanho n.
n Pior caso: maior tempo de execução sobre todas
as entradas de tamanho n.
q Se f é uma função de complexidade baseada na análise de
pior caso, o custo de aplicar o algoritmo nunca é maior do
que f(n).
n Caso médio (ou caso esperado): média dos tempos
de execução de todas as entradas de tamanho n.
Algoritmos e Estrutura de Dados II
Análise de Melhor Caso, Pior Caso
e Caso Médio
n Na análise do caso médio esperado, supõe-se uma
distribuição de probabilidades sobre o conjunto de
entradas de tamanho n e o custo médio é obtido com base
nessa distribuição.
n A análise do caso médio é geralmente muito mais difícil de
obter do que as análises do melhor e do pior caso.
n É comum supor uma distribuição de probabilidades em que
todas as entradas possíveis são igualmente prováveis.
n Na prática isso nem sempre é verdade.
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Considere o problema de acessar os
registros de um arquivo.
n Cada registro contém uma chave única que
é utilizada para recuperar registros do
arquivo.
n O problema: dada uma chave qualquer,
localize o registro que contenha esta chave.
n O algoritmo de pesquisa mais simples é o
que faz a pesquisa sequencial.
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Seja f uma função de complexidade tal que f(n) é o número de
registros consultados no arquivo (número de vezes que a chave
de consulta é comparada com a chave de cada registro).
q melhor caso:
q pior caso:
q caso médio:
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Seja f uma função de complexidade tal que f(n) é o número de
registros consultados no arquivo (número de vezes que a chave
de consulta é comparada com a chave de cada registro).
q melhor caso:
q registro procurado é o primeiro consultado
q pior caso:
q caso médio:
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Seja f uma função de complexidade tal que f(n) é o número de
registros consultados no arquivo (número de vezes que a chave
de consulta é comparada com a chave de cada registro).
q melhor caso:
q registro procurado é o primeiro consultado
q f(n) = 1
q pior caso:
q caso médio:
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Seja f uma função de complexidade tal que f(n) é o número de
registros consultados no arquivo (número de vezes que a chave
de consulta é comparada com a chave de cada registro).
q melhor caso:
q registro procurado é o primeiro consultado
q f(n) = 1
q pior caso:
q registro procurado é o último consultado ou não
está presente no arquivo;
q caso médio:
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Seja f uma função de complexidade tal que f(n) é o número de
registros consultados no arquivo (número de vezes que a chave
de consulta é comparada com a chave de cada registro).
q melhor caso:
q registro procurado é o primeiro consultado
q f(n) = 1
q pior caso:
q registro procurado é o último consultado ou não
está presente no arquivo;
q f(n) = n
q caso médio:
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n No estudo do caso médio, vamos considerar
que toda pesquisa recupera um registro.
n Se pi for a probabilidade de que o i-ésimo
registro seja procurado, e considerando que
para recuperar o i-ésimo registro são
necessárias i comparações, então:
f(n) = 1 x p1 + 2 x p2 + 3 x p3 + ... + n x pn
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Para calcular f(n) basta conhecer a distribuição de
probabilidades pi.
n Se cada registro tiver a mesma probabilidade de ser
acessado que todos os outros, então
pi = 1/n, 1 ≤ i ≤ n
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Para calcular f(n) basta conhecer a distribuição de
probabilidades pi.
n Se cada registro tiver a mesma probabilidade de ser
acessado que todos os outros, então
n Nesse caso:
n A análise do caso esperado revela que uma
pesquisa com sucesso examina aproximadamente
metade dos registros.
pi = 1/n, 1 ≤ i ≤ n
Algoritmos e Estrutura de Dados II
Exemplo - Registros de um Arquivo
n Seja f uma função de complexidade tal que f(n) é o número de
registros consultados no arquivo (número de vezes que a chave
de consulta é comparada com a chave de cada registro).
q melhor caso:
q f(n) = 1
q pior caso:
q f(n) = n
q caso médio:
q f(n) = (n + 1)/2.
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (1)
n Problema: encontrar o maior e o menor elemento de um vetor
de inteiros A[n]; n ≥ 1.
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (1)
n Problema: encontrar o maior e o menor elemento de um vetor
de inteiros A[n]; n ≥ 1.
n Um algoritmo simples pode ser derivado do algoritmo
apresentado no programa para achar o maior elemento.
void MaxMin1(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
if (A[i] < *Min) *Min = A[i];
}
}
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin1?
void MaxMin1(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
if (A[i] < *Min) *Min = A[i];
}
}
2*(n-1)
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin1?
n Seja f(n) o número de comparações entre os
elementos de A, se A contiver n elementos.
n Logo f(n) = 2(n-1) para n > 1, para o melhor caso,
pior caso e caso médio.
void MaxMin1(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
if (A[i] < *Min) *Min = A[i];
}
}
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (2)
n MaxMin1 pode ser facilmente melhorado: a
comparação A[i] < Min só é necessária quando a
comparação A[i] > Max dá falso.
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
void MaxMin2(int A[n], int *Max,
int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
Melhor caso:
Pior caso:
Caso médio:
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Melhor caso:
q quando os elementos estão em ordem crescente;
Pior caso:
Caso médio:
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Melhor caso:
q quando os elementos estão em ordem crescente;
q f(n) = n – 1
Pior caso:
Caso médio:
(n-1)
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Melhor caso:
q quando os elementos estão em ordem crescente;
q f(n) = n – 1
Pior caso:
q quando os elementos estão em ordem decrescente;
Caso médio:
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Melhor caso:
q quando os elementos estão em ordem crescente;
q f(n) = n – 1
Pior caso:
q quando os elementos estão em ordem decrescente;
q f(n) = 2(n – 1)
Caso médio:
(n-1)
(n-1)
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Melhor caso:
q quando os elementos estão em ordem crescente;
q f(n) = n – 1
Pior caso:
q quando os elementos estão em ordem decrescente;
q f(n) = 2(n – 1)
Caso médio:
q No caso médio, A[i] é maior do que Max a metade das vezes.
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin2?
void MaxMin2(int A[n], int *Max, int *Min) {
int i;
*Max = A[0];
*Min = A[0];
for (i = 1; i < n; i++) {
if (A[i] > *Max) *Max = A[i];
else if (A[i] < *Min) *Min = A[i];
}
}
Melhor caso:
q quando os elementos estão em ordem crescente;
q f(n) = n – 1
Pior caso:
q quando os elementos estão em ordem decrescente;
q f(n) = 2(n – 1)
Caso médio:
q No caso médio, A[i] é maior do que Max a metade das vezes.
q f(n) = n – 1 + (n – 1)/2 = 3n/2 – 3/2
(n-1)
(n-1)/2
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (3)
n Podemos fazer melhor ainda para encontrar o mínimo e o
máximo?
10 30 5 68 12 67 22 11 . . .
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (3)
n Considerando o número de comparações realizadas, existe a
possibilidade de obter um algoritmo mais eficiente:
1. Compare os elementos de A aos pares, separando-os em
dois subconjuntos (maiores em um e menores em outro), a
um custo de ⎡n/2⎤ comparações.
2. O máximo é obtido do subconjunto que contém os maiores
elementos, a um custo de ⎡n/2⎤ -1 comparações
3. O mínimo é obtido do subconjunto que contém os menores
elementos, a um custo de ⎡n/2⎤ -1 comparações
10 30 5 68 12 67 22 11 . . .
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (3)
10 30 5 68 12 67 22 11 . . .
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (3)
10 30 5 68 12 67 22 11 . . .
10
30
5 12
68 67 22
11
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para este
novo algoritmo?
n Os elementos de A são comparados dois a dois. Os
elementos maiores são comparados com Max e os
elementos menores são comparados com Min.
n Quando n é ímpar, o elemento que está na posição
A[n-1] é duplicado na posição A[n] para evitar um
tratamento de exceção.
n Para esta implementação:
no pior caso, melhor caso e caso médio
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (3)
void MaxMin3(int n, Vetor A, int *Max, int *Min) {
int i, FimDoAnel;
if ((n % 2) > 0) {
A[n] = A[n - 1];
FimDoAnel = n;
}
else FimDoAnel = n - 1;
if (A[0] > A[1]) {
*Max = A[0]; *Min = A[1];
}
else {
*Max = A[1]; *Min = A[0];
}
i = 3;
while (i <= FimDoAnel) {
if (A[i - 1] > A[i]) {
if (A[i - 1] > *Max) *Max = A[i - 1];
if (A[i] < *Min) *Min = A[i];
}
else {
if (A[i - 1] < *Min) *Min = A[i - 1];
if (A[i] > *Max) *Max = A[i];
}
i += 2;
}
}
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (3)
void MaxMin3(int n, Vetor A, int *Max, int *Min) {
int i, FimDoAnel;
if ((n % 2) > 0) {
A[n] = A[n - 1];
FimDoAnel = n;
}
else FimDoAnel = n - 1;
if (A[0] > A[1]) {
*Max = A[0]; *Min = A[1];
}
else {
*Max = A[1]; *Min = A[0];
}
i = 3;
while (i <= FimDoAnel) {
if (A[i - 1] > A[i]) {
if (A[i - 1] > *Max) *Max = A[i - 1];
if (A[i] < *Min) *Min = A[i];
}
else {
if (A[i - 1] < *Min) *Min = A[i - 1];
if (A[i] > *Max) *Max = A[i];
}
i += 2;
}
}
10 30 5 68 12 67 . . .
Algoritmos e Estrutura de Dados II
Exemplo - Maior e Menor Elemento (3)
void MaxMin3(int n, Vetor A, int *Max, int *Min) {
int i, FimDoAnel;
if ((n % 2) > 0) {
A[n] = A[n - 1];
FimDoAnel = n;
}
else FimDoAnel = n - 1;
if (A[0] > A[1]) {
*Max = A[0]; *Min = A[1];
}
else {
*Max = A[1]; *Min = A[0];
}
i = 3;
while (i <= FimDoAnel) {
if (A[i - 1] > A[i]) {
if (A[i - 1] > *Max) *Max = A[i - 1];
if (A[i] < *Min) *Min = A[i];
}
else {
if (A[i - 1] < *Min) *Min = A[i - 1];
if (A[i] > *Max) *Max = A[i];
}
i += 2;
}
}
Comparação 1
Comparação 2
Comparação 3
Comparação 4
Comparação 3
Comparação 4
10 30 5 68 12 67 . . .
1
(n/2)
- 1
(n/2) - 1
(n/2) - 1
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin3?
n Quantas comparações são feitas em
MaxMin3?
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin3?
n Quantas comparações são feitas em
MaxMin3?
q 1ª. comparação feita 1 vez
q 2ª. comparação feita n/2 - 1 vezes
q 3ª. e 4ª. comparações feitas n/2 – 1 vezes
Algoritmos e Estrutura de Dados II
Qual a função de complexidade para
MaxMin3?
n Quantas comparações são feitas em
MaxMin3?
q 1ª. comparação feita 1 vez
q 2ª. comparação feita n/2 - 1 vezes
q 3ª. e 4ª. comparações feitas n/2 – 1 vezes
f(n) = 1 + n/2 – 1 + 2 * (n/2 – 1)
f(n) = (3n – 6)/2 + 1
f(n) = 3n/2 – 3 + 1 = 3n/2 - 2
Algoritmos e Estrutura de Dados II
Comparação entre os Algoritmos
n A tabela apresenta uma comparação entre os algoritmos dos
programas MaxMin1, MaxMin2 e MaxMin3, considerando o
número de comparações como medida de complexidade.
n Os algoritmos MaxMin2 e MaxMin3 são superiores ao algoritmo
MaxMin1 de forma geral.
n O algoritmo MaxMin3 é superior ao algoritmo MaxMin2 com
relação ao pior caso e bastante próximo quanto ao caso médio.
Algoritmos e Estrutura de Dados II
Exemplo
n Qual é a função de complexidade f(n) para o algoritmo abaixo?
Void funcao(int A[n], int B[n]) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (A[i] > B[j])
A[i] = A[i] + B[j];
else
B[j] = B[j] – A[i];
}
}
}
Algoritmos e Estrutura de Dados II
Limite Inferior - Uso de um Oráculo
n Existe possibilidade de obter um algoritmo MaxMin mais
eficiente?
n Para responder temos de conhecer o limite inferior para essa
classe de algoritmos.
n Como? Uso de um oráculo.
n Dado um modelo de computação que expresse o
comportamento do algoritmo, o oráculo informa o resultado de
cada passo possível (no caso, o resultado de cada comparação).
n Para derivar o limite inferior, o oráculo procura sempre fazer com
que o algoritmo trabalhe o máximo, escolhendo como resultado
da próxima comparação aquele que cause o maior trabalho
possível necessário para determinar a resposta final.
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
n Teorema: Qualquer algoritmo para encontrar o maior e o
menor elemento de um conjunto com n elementos não
ordenados, n>1, faz pelo menos 3n/2 - 2 comparações.
n Prova: A técnica utilizada define um oráculo que descreve o
comportamento do algoritmo utilizando:
n um conjunto de n–tuplas,
n um conjunto de regras associadas que mostram as tuplas
possíveis (estados) que um algoritmo pode assumir a partir
de uma dada tupla e uma única comparação.
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
n Para o problema do maior e menor elemento, utilizamos
uma 4–tupla, representada por (a; b; c; d), onde os
elementos de:
q a: número de elementos nunca comparados;
q b: foram vencedores e nunca perderam em
comparações realizadas (máximo);
q c: foram perdedores e nunca venceramem comparações
realizadas (mínimo);
q d: foram vencedores e perdedores em comparações
realizadas (elementos intermediários).
n O algoritmo inicia no estado (n, 0, 0, 0) e termina com
(0, 1, 1, n - 2).
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
n Após cada comparação, (a; b; c; d) assume um dentre os 6 estados
possíveis abaixo:
q (a - 2, b + 1, c + 1, d) se a ≥ 2 (2 elementos de a são
comparados)
q (a - 1, b + 1, c, d) ou
(a - 1, b, c + 1, d) ou
(a - 1, b, c, d + 1)
se a ≥ 1 (1 elemento de a comparado com 1 de b ou 1 de c)
q (a, b - 1, c, d + 1) se b ≥ 2 (2 elementos de b são comparados)
q (a, b, c - 1, d + 1) se c ≥ 2 (2 elementos de c são comparados)
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
(a, b, c, d)
(n, 0, 0, 0)
(0, 1, 1, n-2)
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
(a, b, c, d)
(n, 0, 0, 0)
comparação de 2 a 2 elementos de a (caminho mais rápido
para zerar a).
(0, n/2, n/2, 0)
(0, 1, 1, n-2)
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
(a, b, c, d)
(n, 0, 0, 0)
comparação de 2 a 2 elementos de a (caminho mais rápido
para zerar a).
(0, n/2, n/2, 0)
comparação de elementos em b para encontrar o máximo
(0, 1, n/2, n/2-1)
(0, 1, 1, n-2)
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
(a, b, c, d)
(n, 0, 0, 0)
comparação de 2 a 2 elementos de a (caminho mais rápido
para zerar a).
(0, n/2, n/2, 0)
comparação de elementos em b para encontrar o máximo
(0, 1, n/2, n/2-1)
comparação de elementos em c para encontrar o mínimo
(0, 1, 1, n-2)
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
(a, b, c, d)
(n, 0, 0, 0)
comparação de 2 a 2 elementos de a (caminho mais rápido
para zerar a).
(0, n/2, n/2, 0)
comparação de elementos em b para encontrar o máximo
(0, 1, n/2, n/2-1)
comparação de elementos em c para encontrar o mínimo
(0, 1, 1, n-2)
n/2
n/2-1
n/2-1
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
n O passo 1 requer necessariamente a manipulação do componente
a.
q O caminho mais rápido para levar a até zero requer n/2
mudanças de estado e termina com a tupla (0, n/2, n/2, 0) (por
meio de comparação dos elementos de a dois a dois).
n A seguir, para reduzir o componente b até um são necessárias n/2
- 1 e mudanças de estado (mínimo de comparações necessárias
para obter o maior elemento de b).
n Idem para c, com n/2 - 1 mudanças de estado.
n Logo, para obter o estado (0, 1, 1, n - 2) a partir do estado (n, 0, 0,
0) são necessárias
n/2 + n/2 - 1 + n/2 - 1= 3n/2 – 2 comparações.
Algoritmos e Estrutura de Dados II
Exemplo de Uso de um Oráculo
n O teorema nos diz que se o número de comparações entre os
elementos de um vetor for utilizado como medida de custo,
então o algoritmo MaxMin3 é ótimo.
Algoritmos e Estrutura de Dados II
Solução
Algoritmos e Estrutura de Dados II
Solução (cont)
__MACOSX/._AEDSII_aula_005_analise_de_complexidade.pdf
AEDSII_aula_006_comportamento_assintotico.pdf
Medida do Tempo de
Execução de um Programa
Livro “Projeto de Algoritmos” – Nívio Ziviani
Capítulo 1 – Subseção 1.3.1
http://www2.dcc.ufmg.br/livros/algoritmos/
(slides adaptados)
Algoritmos e Estrutura de Dados II
Objetivos
n Comportamento Assintótico
n Notações
Ο, Ω, Θ
n Principais Classes de Problemas
n Algoritmos Polinomiais vs. Exponenciais
Algoritmos e Estrutura de Dados II
Comportamento Assintótico de Funções
n O parâmetro n fornece uma medida da dificuldade para se
resolver o problema.
n Algoritmos são parecidos para n pequenos – escolha não é
crítica.
n Análise de algoritmos é realizada para valores grandes de n.
n Comportamento assintótico de f(n): limite do comportamento do
custo quando n cresce.
n Interesse: como o custo aumenta quando n vai para o limite.
Algoritmos e Estrutura de Dados II
Dominação Assintótica
n Definição: Uma função f(n) domina assintoticamente outra
função g(n) se existem duas constantes positivas c e m tais que,
para n ≥ m, temos |g(n)| ≤ c|f(n)|.
Algoritmos e Estrutura de Dados II
Dominação Assintótica
Exemplo 1:
n Sejam f(n) = n2 e g(n) = n
n f(n) domina assintoticamente g(n) desde que
|g(n)| ≤ c|f(n)| para n ≥ m e c > 0
c = 1 e m = 1
n |g(n)| |f(n)|
0 0 0
1 1 1
2 2 4
3 3 9
... ... ...
f(n) domina assintóticamente g(n) se
|g(n)| ≤ c|f(n)| para n ≥ m e c > 0
Algoritmos e Estrutura de Dados II
Dominação Assintótica
Exemplo 2:
n Sejam f(n) = n2 e g(n) = (n+1)2
n f(n) domina assintoticamente g(n)?
c = 4 e n ≥ 1
g(n) ≤ cf(n)
(n+1)2 ≤ 4n2
n2 + 2n + 1 ≤ 4n2
n + 2 + 1/n ≤ 4n
f(n) domina assintóticamente g(n) se
|g(n)| ≤ c|f(n)| para n ≥ m e c > 0
Algoritmos e Estrutura de Dados II
Dominação Assintótica
Exemplo 2:
n Sejam f(n) = n2 e g(n) = (n+1)2
n g(n) domina assintoticamente f(n): c = 1 e n ≥ 1
n2 ≤ (n+1)2
n2 ≤ n2 + 2n + 1
1 ≤ 1 + 2/n + 1/n2
f(n) e g(n) dominam assintoticamente uma a outra
f(n) domina assintóticamente g(n) se
|g(n)| ≤ c|f(n)| para n ≥ m e c > 0
Algoritmos e Estrutura de Dados II
Dominação Assintótica
Exemplo 3:
n Sejam f(n) = n e g(n) = n2
n f(n) domina assintoticamente g(n) desde que
|g(n)| ≤ c|f(n)| para n ≥ m e c > 0
n2 ≤ cn
n ≤ c (x) (ou seja, f(n) não domina assintoticamente g(n))
f(n) domina assintóticamente g(n) se
|g(n)| ≤ c|f(n)| para n ≥ m e c > 0
Notação Assintótica
n Ο - especifica um limite superior para g(n).
g(n) = O(f(n))
n Ω - especifica um limite inferior para g(n).
g(n) = Ω (f(n))
n Θ - especifica um limite firme para g(n).
g(n) = Θ(f(n))
Algoritmos e Estrutura de Dados II
Notação O
n Escrevemos g(n) = O(f(n)) se
n f(n) domina assintoticamente g(n). Lê-se g(n) é da ordem no
máximo f(n).
n Exemplo: quando dizemos que o tempo de execução f(n) de um
programa é O(n²), significa que existem constantes c e m tais que,
para valores de n≥m, f(n) ≤ cn².
Algoritmos e Estrutura de Dados II
Notação O
n Definição: Uma função g(n) é O(f(n)) se existem duas
constantes positivas c e m tais que
g(n) ≤ cf(n), para todo n ≥ m.
Algoritmos e Estrutura de Dados II
Exemplos de Notação O
n Exemplo 4: g(n) = (n + 1)2.
– Logo g(n) é O(n2), quando m = 1 e c = 4.
– Isto porque (n + 1)2 ≤ 4n2 para n ≥ 1.
g(n) é O(f(n)) se g(n) ≤ cf(n), para
todo n ≥ m, onde m e c são positivas
Algoritmos e Estrutura de Dados II
Exemplos de Notação O
n Exemplo 4: g(n) = (n + 1)2.
– Logo g(n) é O(n2), quando m = 1 e c = 4.
– Isto porque (n + 1)2 ≤ 4n2 para n ≥ 1.
n Exemplo 5: g(n) = n e f(n) = n2.
– Sabemos que g(n) é O(n2), pois para n ≥ 0, n ≤ n2.
(n+1) 2 ≤ cn2
n2 + 2n + 1 ≤ cn2
1 + 2/n + 1/n2 ≤ c
g(n) é O(f(n)) se g(n) ≤ cf(n), para
todo n ≥ m, onde m e c são positivas
Algoritmos e Estrutura de Dados II
Exemplos de Notação O
n Exemplo 4: g(n) = (n + 1)2.
– Logo g(n) é O(n2), quando m = 1 e c = 4.
– Isto porque (n + 1)2 ≤ 4n2 para n ≥ 1.
n Exemplo 5: g(n) = n e f(n) = n2.
– Sabemos que g(n) é O(n2), pois para n ≥ 0, n ≤ n2.
– Entretanto f(n) não é O(n).
(n+1) 2 ≤ cn2
n2 + 2n + 1 ≤ cn2
1 + 2/n + 1/n2 ≤ c
g(n) é O(f(n)) se g(n) ≤ cf(n), para
todo n ≥ m, onde m e c são positivas
Algoritmos e Estrutura de Dados II
Exemplos de Notação O
n Exemplo 4: g(n) = (n + 1)2.
– Logo g(n) é O(n2), quando m = 1 e c = 4.
– Isto porque (n + 1)2 ≤ 4n2 para n ≥ 1.
n Exemplo 5: g(n) = n e f(n) = n2.
– Sabemos que g(n) é O(n2), pois para n ≥ 0, n ≤ n2.
– Entretanto f(n) não é O(n).
– Suponha que existam constantes c e m tais que para todo n ≥ m, n2 ≤ cn.
– Logo, c ≥ n para qualquer n ≥ m, e não existe uma constante c que possa
ser maior ou igual a n para todo n.
(n+1) 2 ≤ cn2
n2 + 2n + 1 ≤ cn2
1 + 2/n + 1/n2 ≤ c
g(n) é O(f(n)) se g(n) ≤ cf(n), para
todo n ≥ m, onde m e c são positivas
Algoritmos e Estrutura de Dados II
Exemplos de Notação O
n Exemplo 6: g(n) = 3n3 + 2n2 + n é O(n3).
– Basta mostrar que 3n3 + 2n2 + n ≤ 6n3, para n ≥ 1.
– A função g(n) = 3n3 + 2n2 + n é também O(n4), entretanto esta afirmação é
mais fraca do que dizer que g(n) é O(n3).
3n3 + 2n2 + n ≤ cn4
3 + 2/n + 1/n2 ≤ cn, c=6, m=1
n Exemplo 7: 2n+1 é O(2n)?
g(n) é O(f(n)) se g(n) ≤ cf(n), para
todo n ≥ m, onde m e c são positivas
Algoritmos e Estrutura de Dados II
Operações com a Notação O
Operações com a Notação O
Exemplo 8: regra da soma O(f(n)) + O(g(n)).
n Suponha três trechos cujos tempos de execução são O(n), O(n2) e O(n log
n).
n O tempo de execução dos dois primeiros trechos é O(max(n, n2)), que é
O(n2).
n O tempo de execução de todos os três trechos é então
O(max(n2, n log n)), que é O(n2).
Operações com a Notação O
Exemplo 9: [n + O(1)][n + O(log n) + O(1)]
n2 + O(n log n) + O(n) + O(n) + O(log n) + O(1)
O(n2)
Algoritmos e Estrutura de Dados II
Notação Ω
n Especifica um limite inferior para g(n).
n Definição: Uma função g(n) é Ω(f(n)) se existirem duas constantes
c e m tais que
g(n) ≥ cf(n), para todo n ≥ m.
Algoritmos e Estrutura de Dados II
Notação Ω
n Exemplo 10: Mostrar que g(n) = 3n3 + 2n2 é Ω(n3)
basta fazer c = 1, e então 3n3 + 2n2 ≥ n3 para n ≥ 1.
3 + 2/n ≥ 1 para n ≥ 1
.
g(n) é Ω(f(n)) se g(n) ≥ cf(n), para
todo n ≥ m, onde m e c são positivas
Algoritmos e Estrutura de Dados II
Notação Θ
n Definição: Uma função g(n) é Ө(f(n)) se existirem constantes
positivas c1, c2 e m tais que
0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
n Para todo n ≥ m, a função g(n) é igual a f(n) a menos de uma
constante.
n Neste caso, f(n) é um limite assintótico firme.
Algoritmos e Estrutura de Dados II
Notação Θ
Exemplo 11:
n Mostre que g(n) = n2/2 - 3n é Θ(n2).
c1n2 ≤ n2/2 - 3n ≤ c2n2
c1 ≤ 1/2 - 3/n ≤ c2
O lado direito é verdadeiro para N ≥ 1 com c2 ≥ 1/2 e o lado esquerdo
para n ≥ 7 com c1 ≤ 1/14.
Portanto, escolhendo c1 = 1/14, c2 = 1/2 e m = 7, g(n) = Θ(n2).
G(n) é Θ(f(n)) se 0 ≤ c1f(n) ≤ g(n) ≤
c2f(n), para todo n ≥ m, onde c1 e c2
são positivas.
Algoritmos
e Estrutura de Dados II
Classes de Comportamento Assintótico
• Se f é uma função de complexidade para um algoritmo F, então O(f)
é considerada a complexidade assintótica.
• Dominação assintótica permite comparar funções de complexidade
• Se as funções f e g dominam assintoticamente uma a outra, então os
algoritmos associados são equivalentes.
• O comportamento assintótico não serve para comparar esses
algoritmos
Exemplo: f(n) = n2 e g(n) = (n+1)2
Algoritmos e Estrutura de Dados II
Classes de Comportamento Assintótico
n Por exemplo, considere dois algoritmos F e G aplicados à mesma
classe de problemas, sendo que F leva três vezes o tempo de G ao serem
executados, isto é, f(n) = 3g(n), sendo que O(f(n)) = O(g(n)).
n Logo, o comportamento assintótico não serve para comparar os
algoritmos F e G, porque eles diferem apenas por uma constante.
n Podemos avaliar programas comparando as funções de
complexidade, negligenciando as constantes de proporcionalidade.
Algoritmos e Estrutura de Dados II
Comparação de Programas
n Um programa com tempo de execução O(n) é melhor que outro com
tempo O(n2).
n Porém, as constantes de proporcionalidade podem alterar esta
consideração.
n Exemplo: um programa leva 100n unidades de tempo para ser executado
e outro leva 2n2. Qual dos dois programas é melhor?
- Depende do tamanho do problema:
- Para n < 50, o programa com tempo 2n2 é melhor do que o que
possui tempo 100n.
Algoritmos e Estrutura de Dados II
Principais Classes de Problemas
n f(n) = O(1)
q Complexidade constante.
q Uso do algoritmo independe de n.
q As instruções do algoritmo são executadas um número fixo
de vezes.
void algoritmo1(int *v, int n){
int i, j, aux;
for(i = 0; i < 10; i++){
for(j = 0; j < 9; j++){
if(v[j]>v[j+1]) {
aux=v[j]; v[j]=v[j+1]; v[j+1]=aux;
}
}
}
}
Algoritmos e Estrutura de Dados II
n f(n) = O(n)
q Complexidade linear.
q Em geral, um pequeno trabalho é realizado sobre cada
elemento de entrada
q Cada vez que n dobra de tamanho, o tempo de execução
dobra.
Principais Classes de Problemas
int algoritmo2(int *v, int n, int k){
int i;
for(i = 0; i < n; i++){
if(v[i] == k)
return i;
}
return -1;
}
Algoritmos e Estrutura de Dados II
n f(n) = O(log n)
q Complexidade logarítmica.
q Típico em algoritmos que transformam um problema em
outros menores.
q Quando n é mil, log2n 10, quando n é 1 milhão, log2n 20.
q Exemplo: pesquisa binária
Principais Classes de Problemas
Algoritmos e Estrutura de Dados II
n f(n) = O(n log n)
q Típico em algoritmos que quebram um problema em outros
menores, resolvem cada um deles independentemente e
ajuntando as soluções depois.
q Exemplo: algoritmos de ordenação (mergesort, heapsort)
Principais Classes de Problemas
Algoritmos e Estrutura de Dados II
n f(n) = O(n2)
q Complexidade quadrática.
q Ocorrem quando os itens de dados são processados aos
pares, muitas vezes em um anel dentro de outro.
q Úteis para problemas de tamanhos pequenos.
Principais Classes de Problemas
void algoritmo(int *v, int n){
int i, j, aux;
for(i = 0; i < n; i++){
for(j = 0; j < n-1; j++){
if(v[j]>v[j+1]) {
aux=v[j]; v[j]=v[j+1]; v[j+1]=aux;
}
}
}
}
Algoritmos e Estrutura de Dados II
n f(n) = O(n3)
q Complexidade cúbica.
q Úteis apenas para resolver pequenos problemas.
q Quando n é 100, o número de operações é da ordem de 1
milhão.
q Exemplo: multiplicação de matrizes (algoritmo simples)
Principais Classes de Problemas
Algoritmos e Estrutura de Dados II
n f(n) = O(2n)
q Complexidade exponencial.
q Geralmente não são úteis sob o ponto de vista prático.
q Ocorrem na solução de problemas quando se usa força
bruta para resolvê-los.
q Quando n é 20, o tempo de execução é cerca de 1 milhão.
Quando n dobra, o tempo fica elevado ao quadrado.
Principais Classes de Problemas
Algoritmos e Estrutura de Dados II
n f(n) = O(n!)
q Um algoritmo de complexidade O(n!) é dito ter
complexidade exponencial, apesar de O(n!) ter
comportamento muito pior do que O(2n).
q Geralmente ocorrem quando se usa força bruta para na
solução do problema.
q n = 20 → 20! = 2432902008176640000, um número com
19 dígitos.
q n = 40 → um número com 48 dígitos.
Principais Classes de Problemas
Algoritmos e Estrutura de Dados II
Comparação de Funções de
Complexidade
Algoritmos e Estrutura de Dados II
Comparação de Funções de
Complexidade
(tamanho)
Algoritmos e Estrutura de Dados II
Algoritmos Exponenciais x Polinomiais
n Algoritmo exponencial no tempo de execução tem função de
complexidade O(cn); c > 1.
n Algoritmo polinomial no tempo de execução tem função de
complexidade O(p(n)), onde p(n) é um polinômio.
n A distinção entre estes dois tipos de algoritmos torna-se significativa
quando o tamanho do problema a ser resolvido cresce.
n Por isso, os algoritmos polinomiais são muito mais úteis na prática
do que os exponenciais.
Algoritmos e Estrutura de Dados II
Algoritmos Exponenciais x Polinomiais
n Algoritmos exponenciais são geralmente simples variações de
pesquisa exaustiva.
n Algoritmos polinomiais são geralmente obtidos mediante
entendimento mais profundo da estrutura do problema.
n Um problema é considerado:
q intratável: se não existe um algoritmo polinomial para resolvê-lo.
q bem resolvido: quando existe um algoritmo polinomial para
resolvê-lo.
Algoritmos e Estrutura de Dados II
Algoritmos Exponenciais x
Polinomiais - Exceções
n A distinção entre algoritmos polinomiais eficientes e algoritmos
exponenciais ineficientes possui várias exceções.
n Exemplo: um algoritmo com função de complexidade f(n) = 2n é
mais rápido que um algoritmo g(n) = n5 para valores de n menores
ou iguais a 20.
Algoritmos e Estrutura de Dados II
Exemplo de Algoritmo Exponencial
n Um caixeiro viajante deseja visitar n cidades de tal forma que sua
viagem inicie e termine em uma mesma cidade, e cada cidade deve
ser visitada uma única vez
n Supondo que sempre há uma estrada entre duas cidades quaisquer, o
problema é encontrar a menor rota para a viagem.
Algoritmos e Estrutura de Dados II
Exemplo de Algoritmo Exponencial
n A figura ilustra o exemplo para quatro cidades c1, c2, c3, c4, em que
os números nos arcos indicam a distância entre duas cidades.
n O percurso < c1, c3, c4, c2, c1> é uma solução para o problema,
cujo percurso total tem distância 24.
Algoritmos e Estrutura de Dados II
Exemplo de Algoritmo Exponencial
n Algoritmo simples: verificar todas as rotas e escolher a menor
delas.
n Há (n - 1)! rotas possíveis e a distância total percorrida em cada rota
envolve n adições, logo o número total de adições é n!.
n No exemplo anterior teríamos 24 adições.
n Suponha agora 50 cidades: o número de adições seria 50! ≈ 1064.
n Em um computador que executa 109 adições por segundo, o tempo
total para resolver o problema com 50 cidades seria maior do que
1045 séculos só para executar as adições.
Algoritmos
e Estrutura de Dados II
Exercícios
Exercício 1:
n Mostre que g(n) = log5 n é O(log n).
log5 n ≤ clog n (temos que log5n = log n / log 5)
log n / log 5 ≤ c log n
1/log 5 ≤ c, c = 1 e m = 1
g(n) é O(f(n)) se g(n) ≤ cf(n), para
todo n ≥ m, onde m e c são positivas
AEDSII_aula_007_analise_de_algoritmos.pdf
Algoritmos e Estrutura de Dados II
Técnicas de Análise de Algoritmos
n Determinar o tempo de execução de um programa
pode ser um problema matemático complexo;
n Determinar a ordem do tempo de execução, sem
preocupação com o valor da constante envolvida,
pode ser uma tarefa mais simples.
q manipulação de somas
q produtos,
q permutações,
q fatoriais,
q coeficientes binomiais,
q solução de equações de recorrência
Algoritmos e Estrutura de Dados II
Análise do Tempo de Execução
n Comando de atribuição, de leitura ou de escrita: O(1).
int a;
int v[15];
a = 0;
v[0] = 12;
Algoritmos e Estrutura de Dados II
Análise do Tempo de Execução
n Sequencia de comandos:
n Determinado pelo maior tempo de execução de qualquer
comando da sequencia.
sum = 0;
for (i = 0; i < sqrt(n)/2; i++)
sum++;
for (j = 0; j < sqrt(n)/4; j++)
sum++;
for (k = 0; k < 8+j; k++)
sum++;
Algoritmos e Estrutura de Dados II
Análise do Tempo de Execução
n Comando de decisão:
n Tempo dos comandos dentro do condicional, mais tempo para
avaliar a condição, que é O(1).
if ( A[j] < A[min] )
min = j;
Algoritmos e Estrutura de Dados II
Análise do Tempo de Execução
n Laço:
n Soma do tempo de execução do corpo do laço + o tempo de
avaliar a condição de parada (geralmente O(1)) X número de
iterações.
sum = 0;
for (i = 0; i < sqrt(n)/2; i++) {
if ( A[j] < A[min] )
min = j;
sum++;
}
Algoritmos e Estrutura de Dados II
Análise do Tempo de Execução
n Procedimentos não recursivos:
n Cada um deve ser computado separadamente, iniciando pelos que
não chamam outros procedimentos. Avalia-se então os que são
chamam os já avaliados (utilizando os tempos desses).
n O processo é repetido até chegar no programa principal.
Algoritmos e Estrutura de Dados II
Exemplo 1
void exemplo1 (int n)
{
int i, a;
a=0;
for (i = 0; i < n; i++)
a += i;
}
Qual a Função de Complexidade para o
número de atribuições à variável a?
Qual a Ordem de Complexidade da
função exemplo1 ?
Algoritmos e Estrutura de Dados II
Exemplo 2
void exemplo2 (int n)
{
int i, j, a;
a = 0;
for (i = 0; i < n; i++)
for (j = n; j > i; j--)
a += i + j;
exemplo1(n);
}
Algoritmos e Estrutura de Dados II
Exemplo
Algoritmo de Ordenação
n Seleciona o menor elemento do conjunto.
n Troca este com o primeiro elemento A[0].
n Repita as duas operações acima com os n - 1 elementos
restantes, depois com os n - 2, até que reste apenas um.
Algoritmos e Estrutura de Dados II
Procedimento não Recursivo
Algoritmo para ordenar os n elementos de um conjunto A em ordem ascendente.
)1(
)2(
)3(
)4(
)5(
)6(
)7(
)8(
void Ordena(int* A, int n)
{ /*ordena o vetor A em ordem ascendente*/
int i, j, min,x;
for (i = 0; i < n-1; i++)
{ min = i;
for (j = i; j < n; j++)
if ( A[j] < A[min] )
min = j;
/* troca A[min] e A[i] */
x = A[min];
A[min] = A[i];
A[i] = x;
}
}
Qual a complexidade
em termos do
número de
comparações com
elementos de A?
Algoritmos e Estrutura de Dados II
Procedimento não Recursivo
)1(
)2(
)3(
)4(
)5(
)6(
)7(
)8(
void Ordena(int* A, int n)
{
int i, j, min,x;
for (i = 0; i < n-1; i++)
{ min = i;
for (j = i; j < n; j++)
if ( A[j] < A[min] )
min = j;
/* troca A[min] e A[i] */
x = A[min];
A[min] = A[i];
A[i] = x;
}
}
Laço Interno
n Contém um comando de decisão, com
um comando de atribuição (tempo
constante).
n Quanto ao corpo do comando de decisão,
devemos considerar o pior caso,
assumindo que será sempre executado.
n O tempo para incrementar o índice do
laço e avaliar a condição de terminação é
O(1).
n O tempo combinado para executar uma
vez o laço é O(max(1, 1, 1)) = O(1),
conforme regra da soma para a notação
O
n Como o número de iterações é n - i, o
tempo gasto no laço é O((n - i) x 1) = O(n
- i), conforme regra do produto para a
notação O.
Algoritmos e Estrutura de Dados II
Procedimento não Recursivo
)1(
)2(
)3(
)4(
)5(
)6(
)7(
)8(
void Ordena(int* A, int n)
{
int i, j, min,x;
for (i = 0; i < n-1; i++)
{ min = i;
for (j = i; j < n; j++)
if ( A[j] < A[min] )
min = j;
/* troca A[min] e A[i] */
x = A[min];
A[min] = A[i];
A[i] = x;
}
}
Laço Externo
n Contém, além do laço interno, quatro
comandos de atribuição.
O(max(1, (n - i), 1, 1, 1)) = O(n - i).
n A linha (1) é executada n - 1 vezes, e o
tempo total para executar o programa
está limitado ao produto de uma
constante pelo somatório de (n - i):
n Se considerarmos o número de
comparações como a medida de custo
relevante, o programa faz (n2)/2 - n/2
comparações para ordenar n elementos.
n Se considerarmos o número de trocas, o
programa realiza exatamente n - 1 trocas.
Algoritmos e Estrutura de Dados II
Exercício 1
// Considere A, B e C vetores globais
void p1 (int n)
{
int i, j, k;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
C[i][j]=0;
for (k=n-1; k>=0; k--)
C[i][j]=C[i][j]+A[i][k]*B[k][j];
}
}
O que faz essa função ? Qual
a sua ordem de complexidade?
Algoritmos e Estrutura de Dados II
Exercício 2
void p2 (int n)
{
int i, j, x, y;
x = y = 0;
for (i = 1; i <= n; i++) {
for (j = i; j <= n; j++)
x = x + 1;
for (j = 1; j < i; j++)
y = y + 1;
}
}
Qual a ordem de complexidade
da função p2?
Algoritmos e Estrutura de Dados II
Exercício 3
void Exercicio3(n){
int i, j, a;
for (i=0; i<n; i++){
if (x[i] > 10)
for (j=i+1; j<n; j++)
x[j] = x[j] + 2;
else
x[i] = 1;
j = n-1;
while (j >= 0) {
x[j] = x[j] - 2;
j = j - 1;
}
}
}
Qual a Função de Complexidade
para o número de atribuições
ao vetor x?
AEDSII_aula_008_recursividade.pdf
Recursividade
Seções 2.2 e 1.4 do livro Projeto e
Análise de Algoritmos
Algoritmos e Estrutura
de Dados II
Recursividade
n Um procedimento que chama a si mesmo,
direta ou indiretamente, é dito ser recursivo.
n Recursividade permite descrever algoritmos
de forma mais clara e concisa, especialmente
problemas recursivos por natureza ou que
utilizam estruturas recursivas.
n Exemplos
q Algoritmos de “Dividir para Conquistar”
q Árvores
Algoritmos e Estrutura
de Dados II
Exemplo
n Fatorial:
n! = n*(n-1)! p/ n>0
0! = 1
n Em C
int Fat (int n) {
if (n <= 0)
return 1;
else
return n * Fat(n-1);
}
Algoritmos e Estrutura
de Dados II
Estrutura
n Normalmente, as funções recursivas são
divididas em duas partes
q Chamada Recursiva
q Condição de Parada
n A chamada recursiva pode ser direta (mais
comum) ou indireta (A chama B que chama A
novamente)
n A condição de parada é fundamental para
evitar a execução de loops infinitos
Algoritmos e Estrutura
de Dados II
Execução
n Internamente, quando qualquer chamada de função
é feita dentro de um programa, é criado um
Registro de Ativação na Pilha de Execução do
programa
n O registro de ativação armazena os parâmetros e
variáveis locais da função bem como o “ponto de
retorno” no programa ou subprograma que chamou
essa função.
n Ao final da execução dessa função, o registro é
desempilhado e a execução volta ao subprograma
que chamou a função
Algoritmos e Estrutura
de Dados II
Execução
pilha de execução
topo da pilha
registro de
ativação
Algoritmos e Estrutura
de Dados II
Exemplo
Fat (int n) {
if (n<=0)
return 1;
else
return n * Fat(n-1);
}
main() {
int f;
f = fat(4);
printf(“%d”,f);
} pilha de execução
Algoritmos e Estrutura
de Dados II
Fat (int n) {
if (n<=0)
return 1;
else
return n * Fat(n-1);
}
main() {
int f;
f = fat(4);
printf(“%d”,f);
} pilha de execução
fat(4)
Exemplo
Algoritmos e Estrutura
de Dados II
Fat (int n) {
if (n<=0)
return 1;
else
return n * Fat(n-1);
}
main() {
int f;
f = fat(4);
printf(“%d”,f);
} pilha de execução
fat(4)
fat(3)
Exemplo
Algoritmos e Estrutura
de Dados II
Fat (int n) {
if (n<=0)
return 1;
else
return n * Fat(n-1);
}
main() {
int f;
f = fat(4);
printf(“%d”,f);
} pilha de execução
fat(4)
fat(3)
fat(2)
fat(1)
fat(0)
Exemplo
Algoritmos e Estrutura
de Dados II
Complexidade
n A complexidade de tempo do fatorial recursivo é O(n).
(Em breve iremos ver a maneira de calcular isso
usando equações de recorrência)
n Mas a complexidade de espaço também é O(n),
devido a pilha de execução
n Já no fatorial não recursivo
a complexidade de
espaço é O(1)
Algoritmos e Estrutura
de Dados II
Complexidade
n A complexidade de tempo do fatorial recursivo é O(n).
(Em breve iremos ver a maneira de calcular isso
usando equações de recorrência)
n Mas a complexidade de espaço também é O(n),
devido a pilha de execução
n Já no fatorial não recursivo
a complexidade de
espaço é O(1)
Fat (int n) {
int f;
f = 1;
while(n > 0){
f = f * n;
n = n – 1;
}
return f;
}
Algoritmos e Estrutura
de Dados II
Recursividade
n Portanto, a recursividade nem sempre é a
melhor solução, mesmo quando a definição
matemática do problema é feita em termos
recursivos
Algoritmos e Estrutura
de Dados II
Fibonacci
n Outro exemplo: Série de Fibonacci:
q Fn = Fn-1 + Fn-2 n > 2,
q F1 = F2 = 1
q 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
Fib(int n) {
if (n < 3)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
Algoritmos e Estrutura
de Dados II
Análise da função Fibonacci
n Ineficiência em Fibonacci
q Termos Fn-1 e Fn-2 são computados
independentemente
q Custo para cálculo de Fn
q O(φn) onde φ = (1 + √5)/2 = 1,61803...
q Golden ratio
q Exponencial!!!
Algoritmos e Estrutura
de Dados II
Fibonacci não recursivo
n Complexidade: O(n)
n Conclusão: não usar recursividade
cegamente!
int FibIter(int n) {
int fn1 = 1, fn2 = 1;
int fn, i;
if (n < 3) return 1;
for (i = 3; i <= n; i++) {
fn += fn2 + fn1;
fn2 = fn1;
fn1 = fn;
}
return fn;
}
Algoritmos e Estrutura
de Dados II
Quando vale a pena usar
recursividade
n Recursividade vale a pena para Algoritmos
complexos, cuja a implementação iterativa é
complexa e normalmente requer o uso
explícito de uma pilha
q Dividir para Conquistar (Ex. Quicksort)
q Caminhamento em Árvores (pesquisa)
Algoritmos e Estrutura
de Dados II
Dividir para Conquistar
n Duas chamadas recursivas
q Cada uma resolvendo a metade do problema
n Muito usado na prática
q Solução eficiente de problemas
q Decomposição
n Não produz recomputação excessiva como
fibonacci
q Porções diferentes do problema
Algoritmos e Estrutura
de Dados II
Exemplo: encontrar o máximo
void max(int *v, int e, int d){
int u, v;
int m = (e+d)/2;
if (e == d) return v[e];
u = max(v, e, m);
v = max(v, m+1, d);
if (u > v)
return u;
else
return v;
}
max(v, 0, n-1);
E X E M P L O
0 1 2 3 4 5 6
Algoritmos e Estrutura
de Dados II
Exemplo: régua
void regua(int l, r, h){
int m;
if (h > 0) {
m = (l + r) / 2;
marca(m, h);
regua(l, m, h – 1);
regua(m, r, h – 1);
}
}
Algoritmos e Estrutura
de Dados II
Execução: régua
regua(0, 8, 3)
marca(4, 3)
regua(0, 4, 2)
marca(2, 2)
regua(0, 2, 1)
marca(1, 1)
regua(0, 1, 0)
regua(1, 2, 0)
regua(2, 4, 1)
marca(3, 1)
regua(2, 3, 0)
regua(3, 4, 0)
regua(4, 8, 2)
marca(6, 2)
regua(4, 6, 1)
marca(5, 1)
regua(4, 5, 0)
regua(5, 6, 0)
regua(6, 8, 1)
marca(7, 1)
regua(6, 7, 0)
regua(7, 8, 0)
Algoritmos e Estrutura
de Dados II
Representação por árvore
0, 8, 3
0, 4, 2 4, 8, 2
0, 2, 1 2, 4, 1 4, 6, 1 6, 8, 1
0, 1, 0 1, 2, 0 2, 3, 0 3, 4, 0 4, 5, 0 5, 6, 0 6, 7, 0 7, 8, 0
Algoritmos e Estrutura
de Dados II
Outros exemplos de recursividade
void estrela(int x, y, r)
{
if (r > 0) {
estrela(x-r, y+r, r / 2);
estrela(x+r, y+r, r / 2);
estrela(x-r, y-r, r / 2);
estrela(x+r, y-r, r / 2);
box(x, y, r);
}
}
x e y são as coordenadas do centro.
r o valor da metade do lado
Algoritmos e Estrutura
de Dados II
Outros exemplos de recursividade
void estrela(int x, y, r)
{
if (r > 0) {
estrela(x-r, y+r, r / 2);
estrela(x+r, y+r, r / 2);
estrela(x-r, y-r, r / 2);
estrela(x+r, y-r, r / 2);
box(x, y, r);
}
}
x e y são as coordenadas do centro.
r o valor da metade do lado
Algoritmos e Estrutura
de Dados II
Exercícios
1. Implemente uma função recursiva para
computar o valor de 2n
2. O que faz a função abaixo?
int f(int a, int b) { // considere a > b
if (b == 0)
return a;
else
return f(b, a % b);
}
Algoritmos e Estrutura
de Dados II
Respostas
1. Pot(int n) {
if (n==0)
return 1;
else
return 2 * Pot(n-1);
}
Algoritmos e Estrutura
de Dados II
Respostas
2. Algoritmo de Euclides. Calcula o MDC
(máximo divisor comum) de dois números
a e b
f(18, 12)
f(12, 6)
f(6, 0)
AEDSII_aula_009_analise_algoritmos_recursivos.pdf
Algoritmos e Estrutura de Dados II
Análise de Algoritmos Recursivos
n Para cada procedimento
recursivo é
associada uma função de complexidade f(n)
desconhecida, onde n mede o tamanho dos
argumentos para o procedimento.
n Por se tratar de um algoritmo recursivo, f(n)
vai ser obtida através de uma equação de
recorrência.
n Equação de recorrência: maneira de definir
uma função por uma expressão envolvendo
a mesma função.
Algoritmos e Estrutura de Dados II
Análise de Algoritmos Recursivos
n Tempo de execução de um algoritmo
recursivo: tamanho, número de
subproblemas e o tempo para
decomposição.
n Capturado pela equação de recorrência.
⎩
⎨
⎧
≤=
>+=
cnknT
cn nfbnaTnT
para ,)(
para ),()/()(
Algoritmos e Estrutura de Dados II
Equação de Recorrência
Fat (int n) {
if (n <= 0)
return 1;
else
return n * Fat(n-1);
}
Algoritmos e Estrutura de Dados II
Fat (int n) {
if (n <= 0)
return 1;
else
return n * Fat(n-1);
}
n Equação de recorrência para o Fatorial
T(n) = c + T(n-1), para n > 0
T(n) = d. para n ≤ 0
Equação de Recorrência
Algoritmos e Estrutura de Dados II
Equação de Recorrência
void max(int *v, int e, int d){
int u, v;
int m = (e+d)/2;
if (e == d) return v[e];
u = max(v, e, m);
v = max(v, m+1, d);
if (u > v) return u;
else return v;
}
Algoritmos e Estrutura de Dados II
Equação de Recorrência
void max(int *v, int e, int d){
int u, v;
int m = (e+d)/2;
if (e == d) return v[e];
u = max(v, e, m);
v = max(v, m+1, d);
if (u > v) return u;
else return v;
}
T(n) = 2T(n/2) + 1, para n > 1
T(n) = 0. para n ≤ 1
Algoritmos e Estrutura de Dados II
Exercício 1
n Determine a equação de recorrência para a
função abaixo (operação relevante: atribuição
para vetor X).
void ex(vetor X, int n){
int i;
if (n > 0) {
for(i=0; i<n-1; i++)
X[i] = 0;
X[n] = n;
ex(X,n-1);
}
}
Algoritmos e Estrutura de Dados II
Exercício 1
n Determine a equação de recorrência para a
função abaixo (operação relevante: atribuição
para vetor X).
void ex(vetor X, int n){
int i;
if (n > 0) {
for(i=0; i<n-1; i++)
X[i] = 0;
X[n] = n;
ex(X,n-1);
}
} ⎩
⎨
⎧
≤=
>−+=
0 para ,0)(
0 para ),1()(
nnT
n nTnnT
Algoritmos e Estrutura de Dados II
Outro Exemplo
n Considere a seguinte função:
Pesquisa(n)
{
(1) if (n <= 1)
(2) ‘ inspecione elemento ’ e termine;
else
{
(3) para cada um dos n elementos ‘ inspecione
elemento’;
(4) Pesquisa(n/3) ;
}
}
Algoritmos e Estrutura de Dados II
Outro Exemplo
n Considere a seguinte função:
Pesquisa(n)
{
(1) if (n <= 1)
(2) ‘ inspecione elemento ’ e termine;
else
{
(3) para cada um dos n elementos ‘ inspecione elemento’;
(4) Pesquisa(n/3) ;
}
}
⎩
⎨
⎧
≤=
>+=
1 para ,1)(
1 para ),3/()(
nnT
n nTnnT
Algoritmos e Estrutura de Dados II
Análise de Algoritmos Recursivos
n Abordagem para solução da recorrência:
q Expande a árvore de recursão
q Calcula o custo em cada nível da árvore
q Soma os custos de todos os níveis
q Calcula a fórmula fechada do somatório
Algoritmos e Estrutura de Dados II
Fat (int n) {
if (n <= 0)
return 1;
else
return n * Fat(n-1);
}
n Equação de recorrência para o Fatorial
T(n) = c + T(n-1), para n > 0
T(n) = d. para n ≤ 0
Equação de Recorrência
Algoritmos e Estrutura de Dados II
Equação de Recorrência
Fat (int n) {
if (n <= 0)
return 1;
else
return n * Fat(n-1);
}
n Se n <= 0 faz uma operação de custo
constante
n Se n > 0 faz uma operação de custo
constante e chama recursivamente a função
Algoritmos e Estrutura de Dados II
Equação de Recorrência
Fat (int n) {
if (n <= 0)
return 1;
else
return n * Fat(n-1);
}
n Equação de recorrência para o Fatorial
T(n) = c + T(n-1), para n > 0
T(n) = d. para n ≤ 0
Algoritmos e Estrutura de Dados II
Resolvendo a Equação de Recorrência
n Existem várias formas de se resolver uma equação
de recorrência
n A mais simples é expandir a equação e depois fazer
uma substituição dos termos
n Ex. Fatorial:
T(n) = c + T(n-1)
T(n-1) = c + T(n-2)
T(n-2) = c + T(n-3)
...
T(1) = c + T(0)
T(0) = d
T(n) = c + c + c + ... + c + d
n vezes
T(n) = n.c + d à O(n)
Algoritmos e Estrutura de Dados II
Equação de Recorrência
void max(int *v, int e, int d){
int u, v;
int m = (e+d)/2;
if (e == d) return v[e];
u = max(v, e, m);
v = max(v, m+1, d);
if (u > v) return u;
else return v;
}
T(n) = 2T(n/2) + 1, para n > 1
T(n) = 0. para n ≤ 1
Algoritmos e Estrutura de Dados II
Exercício 1
n Determine a equação de recorrência para a
função abaixo (operação relevante: atribuição
para vetor X). Qual a sua complexidade?
void ex(vetor X, int n){
int i;
if (n > 0) {
for(i=0; i<n-1; i++)
X[i] = 0;
X[n] = n;
ex(X,n-1);
}
} ⎩
⎨
⎧
≤=
>−+=
0 para ,0)(
0 para ),1()(
nnT
n nTnnT
Algoritmos e Estrutura de Dados II
Outro Exemplo
n Equação :
n Essa equação lembra que tipo de problema?
n Como resolver essa equação?
T(n) = 2T(n/2) + n;
T(1) = 1;
T(n) = 2T(n/2) + n;
T(1) = 1;
Algoritmos e Estrutura de Dados II
Resolvendo a Equação
)log.(log.).(log1.2.)2(2)(
:Logo
log12
)1()2(
:Parada de Condição acolocar Para
.)2(2)(
: termosos doSubstituin
)2(2)2(2
)8(8)4(4
)4(4)2(2
)2(2)(
:equação a Expandindo
1)1(
)2(2)(
222
log
2
11
2 nnOnnnnnninTnT
nin
TnT
ninTnT
nnTnT
nnTnT
nnTnT
nnTnT
T
nnTnT
nii
i
i
ii
iiii
=+=+=+=
=→=
→
+=
+=
+=
+=
+=
=
+=
−−
Algoritmos e Estrutura de Dados II
Exercício
n Considere a seguinte função:
Pesquisa(n)
{
(1) if (n <= 1)
(2) ‘ inspecione elemento ’ e termine;
else
{
(3) para cada um dos n elementos ‘ inspecione
elemento’;
(4) Pesquisa(n/3) ;
}
}
Algoritmos e Estrutura de Dados II
Análise da Função Recursiva
n Equação de recorrência
n Resolva a equação de recorrência
q Dicas:
q Pode fazer a simplificação de n será sempre
divisível por 3
q Somatório de uma PG finita:
∑
=
+
−
−
=
n
i
n
i
r
rr
0
1
1
1
⎩
⎨
⎧
≤=
>+=
1 para ,1)(
1 para ),3/()(
nnT
n nTnnT
Algoritmos e Estrutura de Dados II
Resolvendo a equação
n Substitui-se os termos T(k), k < n, até que todos os termos
T(k), k > 1, tenham sido substituídos por fórmulas contendo
apenas T(1).
1 → n/3K = 1 → n = 3K 1
Algoritmos e Estrutura de Dados II
Resolvendo a equação
Considerando que T(n/3K) = T(1) temos:
Aplicando a fórmula do somatório de uma PG
finita temos:
O(n)
∑
=
+
−
−
=
n
i
n
i
r
rr
0
1
1
1
1
3
1)1(
3
)(
1
0
1
0
+=+= ∑∑
−
=
−
=
k
i
i
k
i
i nT
nnT
2123
)3/2()1(1
)3/2())/1(1(1
)3/11())3/1(1(1
−
−+
−+
−−+
n
n
nn
n k
Algoritmos e Estrutura de Dados II
Teorema Mestre
n Método “receita de bolo” para resolver
recorrências do tipo
n Este tipo de recorrência é típico de
algoritmos “dividir para conquistar”
q Dividem um problema em a subproblemas
q Cada subproblema tem tamanho n/b
q Custo para dividir e combinar os resultados é f(n)
positiva )( e , onde
)()/()(
nfba
nfbnaTnT
11 >≥
+=
Algoritmos e Estrutura de Dados II
Teorema Mestre
n Seja
)()/()( nfbnaTnT +=
)).((Θ)( temos
, para )()/( se e para )(Ω)( Se
).log(Θ)( temos
,)(Θ)( Se
).(Θ)( temos
, com ,)()( Se
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
=
<≤>=
=
=
=
>=
+
−
10
0
�
�
�
�
Algoritmos e Estrutura de Dados II
Teorema Mestre
n O resultado da recorrência depende da
comparação entre
n Note que a diferença entre
tem que ser polinomial, isto é, tem que ser
pelo menos
abnnf log e )(
abnnf log e )(
�n
Teorema Mestre (1)
n Resolva a recorrência
usando o teorema mestre
n Caso 1 se aplica, temos
nnTnT += )/()( 39
)(Θ)( 2nnT =
)).(()( temos
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos
,)()( Se 2.
).()( temos
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
• g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m
• g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m
• g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
Teorema Mestre (2)
n Resolva a recorrência
usando o teorema mestre
n Caso 2 se aplica, temos
132 += )/()( nTnT
))(log(Θ)( nnT =
)).(()( temos
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos
,)()( Se 2.
).()( temos
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
• g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m
• g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m
• g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
Teorema Mestre (3)
n Resolva a recorrência
usando o teorema mestre
n Caso 3 se aplica, temos
nnnTnT log)4/(3)( +=
)log()( nnnT Θ=
)).(()( temos
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos
,)()( Se 2.
).()( temos
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
• g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m
• g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m
• g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
Teorema Mestre (4)
n Novamente a equação de recorrência:
T(n) = 2T(n/2) + n;
T(1) = 1;
T(n) = 2T(n/2) + n;
T(1) = 1;
)).(()( temos
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos
,)()( Se 2.
).()( temos
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
• g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m
• g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m
• g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
Algoritmos e Estrutura de Dados II
Teorema Mestre (5)
n Resolva a recorrência
n Nenhum caso do teorema mestre de aplica
nnnTnT log)/()( += 22
T(n) = 2T(n/2) + n;
T(1) = 1;
)).(()( temos
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos
,)()( Se 2.
).()( temos
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
• g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m
• g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m
• g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
AEDSII_aula_010_exercicios_complexidade.pdf
Complexidade
de
algoritmos
Exemplos
e
exercícios
Exemplo
1
int find ( int a[], int n, int x )
{
int i;
for ( i = 0; i < n; i++ )
{
if ( a[i] == x )
return i;
}
return 0;
}
Exemplo
2
int find ( int a[], int n, int x )
{
int i = 0, mid;
while ( i < n ) {
mid = ( n + i ) / 2;
if ( a[mid] < x )
n = mid;
else if ( a[mid] > x )
i = mid + 1;
else return mid;
}
return 0;
}
Exemplo
3
void bubbleSort(int *array, int size)
{
int swapped = 0;
int x;
do {
swapped = 0;
for (x = 0; x < size-1;x++) {
if (array[x]>array[x+1]) {
swap(&array[x], &array[x+1]);
swapped = 1;
}
}
} while (swapped);
}
Exemplo
4
void insert(int *array, int pos, int value)
{
pos--;
while (pos >= 0 && array[pos] > value) {
array[pos+1] = array[pos];
pos--;
}
array[pos+1] = value;
}
void insertionSort(int *array, int size)
{
int x;
for (x = 0; x < size; x++) {
insert(array, x, array[x]);
}
}
Exemplo
5
int Exemplo5(int N, int M) {
int result=0, x=0, i, j, k;
for (i = 0; i < N; i++)
for (j = i; j < N; j++) {
for (k = 0; k < M; k++) {
x=0;
while (x<N) {
result++;
x+=3;
}
}
for (k = 0; k < 2*M; k++)
if (k % 7 == 4) result++;
}
return result;
}
Exemplo
6
#define X 0
#define Y 1
int Area2(Point a, b, c) {
return (a[X]*b[Y] – a[Y]*b[X]
+ a[Y]*c[X] – a[X]*c[Y]
+ b[X]*c[Y] - c[X]*b[Y]);
}
int AreaPoligono2(Polygon P) {
int i, sum = 0;
for (i = 1; i < P.numvertices - 1; i++)
sum += Area2(P[0], P[i], P[i+1]);
return sum;
}
Exemplo
7
#define MAX 1000
int Escolhe(int k); // funcao com custo O(n^2)
int Transfere(int k); // funcao com custo O(log n)
void
main() {
int i, n, sum = 0;
int vetor[MAX];
scanf(“%d”, &n);
for (i = 0; i < n; i++)
vetor[i] = rand() % 50; // inteiro entre 0 e 49
for (i = 0; i < n; i++) {
for (j = 0; j < vetor[i]; j++) {
if (vetor[j] < vetor[i])
vetor[j] = Escolhe(vetor[i]);
else
vetor[j] = vetor[i];
}
k = vetor[i];
while (k > 0) {
Transfere(vetor[k]);
k--;
}
}
}
Algoritmos e Estrutura de Dados II
Teorema Mestre
T(n) = 2T(n/2) + n;
T(1) = 1;
)).(()( temos
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos
,)()( Se 2.
).()( temos
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
• g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m
• g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m
• g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m
Algoritmos e Estrutura de Dados II
Ex. 1
T(n) = 2T(n/2) + n;
T(1) = 1;
int main() {
int i, ia, ib, x, n;
int A[10]={ . . . };
int B[10]={ . . . };
A[11] = -∞;
B[11] = -∞;
cout<<"\nEntre com o valor de n p/ achar o n-esimo
maior elemento:";
cin>>n;
if (n <= |A| + |B|) {
ia = 1;
ib = 1;
for (i = 0; i < n; i++)
if (A[ia] > B[ib]) {
x = A[ia];
ia++;
}
else {
x = B[ib];
ib++;
}
}
cout<<i<<"-esimo maior elemento = "<<x;
}
Algoritmos e Estrutura de Dados II
Ex. 2
T(n) = 2T(n/2) + n;
T(1) = 1;
esq = 1;
dir = n;
achou = false;
while (!achou && esq < dir){
i = (esq + dir)/2;
if (A[i] >= x)
if (A[i+1] <= x)
achou = true;
else
esq = i+1;
else
dir = i;
}
if (achou)
cout<<"\nSera inserido na posicao "<<i+1;
else {
i = (esq + dir)/2;
if (x > A[i])
cout<<"\nSera inserido na posicao "<<i;
else
cout<<"\nSera inserido na posicao "<<i+1;
}
Algoritmos e Estrutura de Dados II
Ex. 3
T(n) = 2T(n/2) + n;
T(1) = 1;
int somatorio(int a) {
int soma, i;
soma = 0;
for (i = 1; i <= a; i++)
soma := soma + i;
return soma;
end;
Algoritmos e Estrutura de Dados II
Ex. 5
T(n) = 2T(n/2) + n;
T(1) = 1;
typedef char TipoTexto[MaxTexto];
typedef char TipoPadrao[MaxPadrao];
void ForcaBruta (TipoTexto T, int n, TipoPadrao P, int m)
//-- Pesquisa o padrao P[0..m-1] no texto T[0..n-1] –
{
int i, j, k;
for (i = 0; i < n; i++) {
k = i; j = 0;
while ((j < m) && (T[k] == P[j])) {
k++;
j++;
}
if (j == m) {
printf("Casamento na posicao %d\n", i);
break; // sai do for
}
}
}
AEDSII_aula_011_alocacao_dinamica.pdf
The image cannot be displayed. Your computer may not have
enough memory to open the image, or the image may have
been corrupted. Restart your computer, and then open the file
again. If the red x still appears, you may have to delete the
image and then insert it again.
The image
cannot be
displayed.
Your
computer
may not
have
enough
memory to
open the
image, or
the image
may have
Alocação Dinâmica de
Memória
Gisele L. Pappa
Algoritmos e Estruturas de Dados II
DCC – UFMG
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Alocação Estática x Dinâmica
n C: dois tipos de alocação de memória: Estática e
Dinâmica
n Na alocação estática, o espaço para as variáveis é
reservado no início da execução, não podendo ser
alterado depois
q int a; int b[20];
n Na alocação dinâmica, o espaço para as variáveis
pode ser alocado dinamicamente durante a
execução do programa
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Organização da Memória
Algoritmos e Estrutura de Dados II
Informação sobre funções
Código compilado
Memória Dinâmica
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Alocação Dinâmica
n As variáveis alocadas dinamicamente são
chamadas de Apontadores (pointers) pois
na verdade elas armazenam o endereço de
memória de uma variável
n A memória alocada dinamicamente faz parte
de uma área de memória chamada heap
q Basicamente, o programa aloca e desaloca
porções de memória do heap durante a execução
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Esquema de Memória
Memória Estática
0x016 a
0x020 b
10
0X234
10
a é um int
b é um apontador para um int
Heap
0X214
0X218
0X222
0X226
0X230
0X234
0X238
0X240
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Acesso a partir de Apontadores
n Acessar o valor da variável: endereço de
memória armazenado
n Acessar o conteúdo que associado ao
endereço de memória armazenado
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Liberação de Memória
n A memória deve ser liberada após o término
de seu uso
n A liberação deve ser feita por quem fez a
alocação:
q Estática: compilador
q Dinâmica: programador
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Apontadores – Notação
n definição de p como um apontador para uma variável do tipo Tipo
q Tipo *p;
n Alocação de memória para uma variável apontada por p
q p = (Tipo*) malloc(sizeof(Tipo));
n Liberação de memória
q free(p);
n Conteudo da variável apontada por P
q *p;
n Valor nulo para um apontador
q NULL;
n Endereço de uma variável a
q &a;
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Alocação Dinâmica
int *a, b;
...
b = 10;
a = (int *) malloc(sizeof(int));
*a = 20;
a = &b;
a
20
b
Heap Alocação
Estática
10
X
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Alocação Dinâmica
int b;
int *a;
b = 10;
a = (int *) malloc(sizeof(int));
*a = 20;
printf("%d\n", a[0]);
a = &b;
printf("%d\n", a[0]);
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Erros Comuns
n Esquecer de alocar memória e tentar
acessar o conteúdo da variável
n Copiar o valor do apontador ao invés do
valor da variável apontada
n Esquecer de desalocar memória
q Ela é desalocada ao fim do programa ou
procedimento função onde a variável está
declarada, mas pode ser um problema em loops
n Tentar acessar o conteúdo da variável
depois de desalocá-la
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Exercício: C
double a;
double *p;
a = 3.14;
printf("%f\n", a);
p = &a;
*p = 2.718;
printf("%f\n", a);
a = 5;
printf("%f\n", *p);
p = NULL;
p = (double *)malloc(sizeof(double));
*p = 20;
printf("%f\n", *p);
printf("%f\n", a);
free(p);
printf("%f\n", *p);
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Pergunta que não quer calar...
int *a não é a declaração de um vetor de int?
n Em C, todo vetor é um apontador.
n Portanto pode-se fazer coisas como:
int a[10], *b;
b = a;
b[5] = 100;
printf(“%d\n”, a[5]);
printf(“%d\n”, b[5]);
int a[10], *b;
b = (int *) malloc(10*sizeof(int));
b[5] = 100;
printf(“%d\n”, a[5]);
Printf(“%d\n”, b[5]);
100
100
42657
100
Obs. Não se pode fazer a = b
no exemplo acima
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Apontadores para Tipos Estruturados
n Apontadores são normalmente utilizados
com tipos estruturados
Typedef struct {
int idade;
double salario;
} TRegistro
TRegistro *a;
...
a = (TRegistro *) malloc(sizeof(TRegistro))
a->idade = 30; /* *a.idade = 30 */
a->salario = 80;
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Passagem de Parâmetros
n Em pascal, parâmetros para função podem ser
passados por valor ou por referência
q Por valor: o parâmetro formal (recebido no procedimento)
é uma cópia do parâmetro real (passado na chamada)
q Por referência: o parâmetro formal (recebido no
procedimento) é uma referência para o parâmetro real
(passado na chamada)
q Usa-se o termo var precedendo o parâmetro formal
n Em C só existe passagem por valor, logo deve-se
implementar a passagem por referência utilizando-
se apontadores
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Passagem de Parâmetros (C)
void SomaUm(int x, int *y)
{
x = x + 1;
*y = (*y) + 1;
printf("Funcao SomaUm: %d %d\n", x, *y);
}
int main()
{
int a=0, b=0;
SomaUm(a, &b);
printf("Programa principal: %d %d\n", a, b);
}
1 1
0 1
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Passagem de Parâmetros
n E para alocar memória dentro de um procedimento?
q Em pascal, basta passar a variável (apontador) como
referência.
q Em C também, mas como não há passagem por referência
as coisas são um pouco mais complicadas
void aloca(int *x, int n)
{
x=(int *)malloc(n*sizeof(int));
x[0] = 20;
}
int main()
{
int *a;
aloca(a, 10);
a[1] = 40;
}
Error!
Access Violation!
void aloca(int **x, int n)
{
*x=(int *)malloc(n*sizeof(int));
*x[0] = 20;
}
int main()
{
int *a;
aloca(&a, 10);
a[1] = 40;
}
OK
The image cannot be displayed.
Your computer may not have
enough memory to open the image,
or the image may have been
corrupted. Restart your computer,
and then open the file again. If the
The
ima
ge
can
not
be
disp
laye
d.
Algoritmos e Estrutura de Dados II
Exercício
n Criar um tipo que é uma estrutura que represente
uma pessoa, contendo nome, data de nascimento e
CPF.
n Criar uma variável que é um ponteiro para esta
estrutura (no programa principal)
n Criar uma função que recebe este ponteiro e
preenche os dados da estrutura
n Criar uma função que recebe este ponteiro e imprime
os dados da estrutura
n Fazer a chamada a esta função na função principal
AEDSII_aula_012_listas_lineares.pdf
Listas Lineares
Livro “Projeto de Algoritmos” – Nívio Ziviani
Capítulo 3 – Seção 3.1
http://www2.dcc.ufmg.br/livros/algoritmos/
(adaptado)
Algoritmos e Estrutura de Dados II
Agenda
n Listas lineares
n TAD para listas lineares
n Alocação sequencial
n Alocação encadeada
Algoritmos e Estrutura de Dados II
Listas Lineares
n Maneira de representar elementos de um
conjunto.
n Itens podem ser acessados, inseridos ou
retirados de uma lista.
n Podem crescer ou diminuir de tamanho
durante a execução.
n Adequadas quando não é possível prever a
demanda por memória
Algoritmos e Estrutura de Dados II
Definição de Listas Lineares
n Sequência de zero ou mais itens
q x1 ,x2 ,···,xn , na qual xi é de um determinado tipo e n representa
o tamanho da lista linear.
n Sua principal propriedade estrutural envolve as posições
relativas dos itens em uma dimensão.
q Assumindo n ≥ 1, x1 é o primeiro item
da lista e xn é o último item
da lista.
q xi precede xi+1 para i = 1,2,···,n – 1
q xi sucede xi-1 para i = 2,3,···,n
q o elemento xi é dito estar na i-ésima posição da lista.
Algoritmos e Estrutura de Dados II
Listas Lineares
NULL
struct Aluno {
string nome;
int matricula;
char conceito;
};
Algoritmos e Estrutura de Dados II
TAD Listas Lineares
n TAD: Agrupa a estrutura de dados juntamente com as
operações que podem ser feitas sobre esses dados.
n Operações para listas lineares.
struct Aluno {
string nome;
int matricula;
char conceito;
};
NULL
Algoritmos e Estrutura de Dados II
n O conjunto de operações a ser definido depende de cada
aplicação.
n Um conjunto de operações necessário a uma maioria de
aplicações é:
1) Criar uma lista linear vazia.
2) Inserir um novo item imediatamente após o i-ésimo item.
3) Retirar o i-ésimo item.
4) Localizar o i-ésimo item para examinar e/ou alterar o conteúdo de seus
componentes.
5) Combinar duas ou mais listas lineares em uma lista única.
6) Partir uma lista linear em duas ou mais listas.
7) Fazer uma cópia da lista linear.
8) Ordenar os itens da lista em ordem ascendente ou descendente, de
acordo com alguns de seus componentes.
9) Pesquisar a ocorrência de um item com um valor particular em algum
componente.
TAD Listas Lineares
Algoritmos e Estrutura de Dados II
Implementações de Listas Lineares
n As duas representações mais utilizadas são as
implementações
q Alocação sequencial (arranjo) e encadeada.
n Exemplo de Conjunto de Operações:
1) FLVazia(Lista). Faz a lista ficar vazia.
2) Insere(x, Lista). Insere x após o último item da lista.
3) Retira(p, Lista, x). Retorna o item x que está na posição p da lista,
retirando-o da lista e deslocando os itens a partir da posição p+1 para
as posições anteriores.
4) Vazia(Lista). Esta função retorna true se lista vazia; senão retorna false.
5) Imprime(Lista). Imprime os itens da lista na ordem de ocorrência.
Algoritmos e Estrutura de Dados II
Alocação Sequencial
n Localização na memória:
q Posições contíguas.
n Visita:
q Pode ser percorrida em qualquer direção.
q Permite acesso aleatório.
n Inserção:
q Realizada após o último item com custo constante.
q Um novo item no meio da lista custo não
constante.
n Remoção:
q Final da lista: custo constante
q Meio ou início: requer deslocamento de itens
Algoritmos e Estrutura de Dados II
Alocação Sequencial (estrutura)
n Os itens armazenados em um array.
n MaxTam define o tamanho máximo
permitido para a lista.
n O campo Último aponta para a posição
seguinte a do último elemento da lista.
(primeira posição vazia)
n O i-ésimo item da lista está armazenado
na i-ésima-1 posição do array, 0 ≤ i <
Último. (Item[i])
#define InicioArranjo 0
#define MaxTam 1000
typedef int TipoChave;
typedef int Apontador;
typedef struct {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct {
TipoItem Item[MaxTam];
Apontador Primeiro, Ultimo;
} TipoLista;
Item
Algoritmos e Estrutura de Dados II
Alocação Sequencial (estrutura)
n Os itens armazenados em um array.
n MaxTam define o tamanho máximo
permitido para a lista.
n O campo Último aponta para a posição
seguinte a do último elemento da lista.
(primeira posição vazia)
n O i-ésimo item da lista está armazenado
na i-ésima-1 posição do array, 0 ≤ i <
Último. (Item[i])
#define InicioArranjo 0
#define MaxTam 1000
typedef int TipoChave;
typedef int Apontador;
typedef struct {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct {
TipoItem Item[MaxTam];
Apontador Primeiro, Ultimo;
} TipoLista;
Item
Alocação Sequencial (estrutura)
n Os itens armazenados em um array.
n MaxTam define o tamanho máximo
permitido para a lista.
n O campo Último aponta para a posição
seguinte a do último elemento da lista.
(primeira posição vazia)
n O i-ésimo item da lista está armazenado
na i-ésima-1 posição do array, 0 ≤ i <
Último. (Item[i])
#define InicioArranjo 0
#define MaxTam 1000
typedef int TipoChave;
typedef int Apontador;
typedef struct {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct {
TipoItem Item[MaxTam];
Apontador Primeiro, Ultimo;
} TipoLista;
Item
Alocação Sequencial (estrutura)
n Os itens armazenados em um array.
n MaxTam define o tamanho máximo
permitido para a lista.
n O campo Último aponta para a posição
seguinte a do último elemento da lista.
(primeira posição vazia)
n O i-ésimo item da lista está armazenado
na i-ésima-1 posição do array, 0 ≤ i <
Último. (Item[i])
#define InicioArranjo 0
#define MaxTam 1000
typedef int TipoChave;
typedef int Apontador;
typedef struct {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct {
TipoItem Item[MaxTam];
Apontador Primeiro, Ultimo;
} TipoLista; Ultimo
Primeiro
MaxTam
Item[0]
Item[1]
Item
/* faz lista ficar vazia */
void FLVazia(TipoLista *Lista)
{
Lista->Primeiro = InicioArranjo;
Lista->Ultimo = Lista->Primeiro;
} /* FLVazia */
Alocação Sequencial (operações)
???
???
???
???
…
???
MaxTam
/* faz lista ficar vazia */
void FLVazia(TipoLista *Lista)
{
Lista->Primeiro = InicioArranjo;
Lista->Ultimo = Lista->Primeiro;
} /* FLVazia */
Alocação Sequencial (operações)
???
???
???
???
…
???
MaxTam
Ultimo
Primeiro
/* faz lista ficar vazia */
void FLVazia(TipoLista *Lista)
{
Lista->Primeiro = InicioArranjo;
Lista->Ultimo = Lista->Primeiro;
} /* FLVazia */
/* testa se a lista está vazia */
int Vazia(TipoLista *Lista)
{
return (Lista->Primeiro == Lista->Ultimo);
} /* Vazia */
Alocação Sequencial (operações)
???
???
???
???
…
???
MaxTam
Ultimo
Primeiro
void Insere(TipoItem x, TipoLista *Lista)
{
if (Lista->Ultimo >= MaxTam)
printf("Lista esta cheia\n");
else
{
Lista->Item[Lista->Ultimo] = x;
Lista->Ultimo++;
}
} /* Insere */
Alocação Sequencial (operações)
???
???
???
???
…
???
MaxTam
Ultimo
Primeiro
void Insere(TipoItem x, TipoLista *Lista)
{
if (Lista->Ultimo >= MaxTam)
printf("Lista esta cheia\n");
else
{
Lista->Item[Lista->Ultimo] = x;
Lista->Ultimo++;
}
} /* Insere */
Alocação Sequencial (operações)
???
???
???
???
…
???
MaxTam
Ultimo
Primeiro
x
???
???
???
…
???
MaxTam
Ultimo
Primeiro
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) {
int Aux;
if (Vazia(Lista) || p >= Lista->Ultimo) {
printf("Erro: Posicao nao existe\n");
return;
}
*Item = Lista->Item[p];
Lista->Ultimo--;
for (Aux = p+1; Aux <= Lista->Ultimo; Aux++)
Lista->Item[Aux - 1] = Lista->Item[Aux];
}
Alocação Sequencial (operações)
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) {
int Aux;
if (Vazia(Lista) || p >= Lista->Ultimo) {
printf("Erro: Posicao nao
existe\n");
return;
}
*Item = Lista->Item[p];
Lista->Ultimo--;
for (Aux = p+1; Aux <= Lista->Ultimo; Aux++)
Lista->Item[Aux - 1] = Lista->Item[Aux];
}
x1
x2
x3
x4
???
??? Ultimo
Primeiro
p
Alocação Sequencial (operações)
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) {
int Aux;
if (Vazia(Lista) || p >= Lista->Ultimo) {
printf("Erro: Posicao nao existe\n");
return;
}
*Item = Lista->Item[p];
Lista->Ultimo--;
for (Aux = p+1; Aux <= Lista->Ultimo; Aux++)
Lista->Item[Aux - 1] = Lista->Item[Aux];
}
x1
x2
x3
x4
???
???
Ultimo
Primeiro
p
Alocação Sequencial (operações)
x1
x2
x3
x4
???
??? Ultimo
Primeiro
p
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) {
int Aux;
if (Vazia(Lista) || p >= Lista->Ultimo) {
printf("Erro: Posicao nao existe\n");
return;
}
*Item = Lista->Item[p];
Lista->Ultimo--;
for (Aux = p+1; Aux <= Lista->Ultimo; Aux++)
Lista->Item[Aux - 1] = Lista->Item[Aux];
}
x1
x3
x4
??? (x4)
…
???
Ultimo
Primeiro
Alocação Sequencial (operações)
x1
x2
x3
x4
???
???
Ultimo
Primeiro
p
x1
x2
x3
x4
???
??? Ultimo
Primeiro
p
void Imprime(TipoLista *Lista)
{
Apontador i;
for (i = Lista->Primeiro; i < Lista->Ultimo; i++)
printf("%d\n", Lista->Item[i].Chave);
}
x1
x2
x3
???
…
???
Ultimo
Primeiro
Alocação Sequencial (operações)
n Vantagens:
q economia de memória (os apontadores são implícitos nesta
estrutura).
q Acesso a um item qualquer é O(1).
n Desvantagens:
q custo para inserir ou retirar itens da lista, que pode causar um
deslocamento de todos os itens, no pior caso; O(n)
q em aplicações em que não existe previsão sobre o crescimento
da lista, a utilização de arranjos em linguagens como o Pascal
pode ser problemática porque neste caso o tamanho máximo
da lista tem de ser definido em tempo de compilação.
Alocação Sequencial (vantagens e
desvantagens)
Alocação Encadeada
n Cada item é encadeado com o seguinte mediante uma
variável do tipo Apontador.
n Permite utilizar posições não contíguas de memória.
n É possível inserir e retirar elementos sem necessidade de
deslocar os itens seguintes da lista.
n Há uma célula cabeça para simplificar as operações sobre a
lista.
Alocação Encadeada
n A lista é constituída de células.
n Cada célula contém um item da lista e um apontador
para a célula seguinte.
n O registro TipoLista contém um apontador para a célula
cabeça e um apontador para a última célula da lista.
Algoritmos e Estrutura de Dados II
Alocação Encadeada
n Localização na memória:
q Posições não sequenciais.
n Visita:
q Apenas na direção xi para xi+1.
q Permite apenas acesso sequencial.
n Inserção:
q Realizada em qualquer posição com custo
constante.
n Remoção:
q Custo constante em qualquer posição.
Algoritmos e Estrutura de Dados II
Alocação Encadeada
n Características:
q Tamanho da lista não é pré-definido
q Cada elemento guarda quem é o próximo
q Elementos não estão contíguos na memória
info
info
prox
info
NULL
info
NULL
info
NULL
prox
prox
© R. O. Prates
Algoritmos e Estrutura de Dados II
Sobre os Elementos da Lista
n Elemento: guarda as informações sobre
cada elemento.
n Para isso define-se cada elemento como
uma estrutura que possui:
q campos de informações
q ponteiro para o próximo elemento
info
prox
© R. O. Prates
Sobre a Lista
n Uma lista é definida como um apontador
para a primeira célula
n Uma lista pode ter uma célula cabeça
info
prox prox
info
prox
info
NULL
n Uma lista pode ter um apontador para o
último elemento
Último
Primeiro
© R. O. Prates
Implementação em C
typedef int TipoChave;
typedef struct {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct Celula_str *Apontador;
typedef struct Celula_str {
TipoItem Item;
Apontador Prox;
} Celula;
typedef struct {
Apontador Primeiro, Ultimo;
} TipoLista;
© R. O. Prates
Último
Primeiro
TipoLista
Prox
Item
Celula
Prox
Item
Celula
Cria Lista Vazia
NULL
Cabeça
Último
Primeiro
void FLVazia(TipoLista *Lista)
{
Lista->Primeiro = (Apontador) malloc(sizeof(Celula));
Lista->Ultimo = Lista->Primeiro;
Lista->Primeiro->Prox = NULL;
}
int Vazia(TipoLista Lista)
{
return (Lista.Primeiro == Lista.Ultimo);
}
© R. O. Prates
Inserção de Elementos na Lista
info
prox prox
info
prox
info
NULL
Último
n 3 opções de posição onde pode inserir:
q 1ª. posição
q última posição
q Após um elemento qualquer E
Primeiro
© R. O. Prates
Inserção na Primeira Posição
info
prox prox
info
prox
info
NULL
Último
info
NULL prox
Primeiro
Novo
© R. O. Prates
Inserção na Última Posição
info
prox prox
info
prox
info
NULL
Último
info
NULL prox
Primeiro
Novo
© R. O. Prates
Inserção na Após o Elemento E
prox
info
prox
info
NULL
Último
info
NULL prox
Elem E
info
prox
Primeiro
Novo
© R. O. Prates
Inserção de Elementos na Lista
n Na verdade, as 3 opções de inserção são
equivalentes a inserir após uma célula
apontada por p
q 1ª. posição (p é a célula cabeça)
q Última posição (p é o último)
q Após um elemento qualquer E (p aponta para E)
© R. O. Prates
Inserção na Após o Elemento E
prox
info
prox
info
NULL
Último
info
NULL prox
Elem E
info
prox
Primeiro
x
© R. O. Prates
void Insere(TipoItem x, TipoLista *lista, Apontador E){
Apontador novo;
novo = (Apontador) malloc(sizeof(Celula));
novo->Item = x;
novo->prox = E->prox;
E->prox = novo;
}
Retirada de Elementos na Lista
info
prox prox
info
prox
info
NULL
Último
n 3 opções de posição de onde pode retirar:
q 1ª. posição
q última posição
q Um elemento qualquer E
© R. O. Prates
Retirada do Elemento na
Primeira Posição da Lista
info
prox prox
info
prox
info
NULL
Último
Primeiro
Temp
© R. O. Prates
Retirada do Elemento E da Lista
info
prox prox
info
prox
info
NULL
Último
Elem E
Anterior Primeiro
© R. O. Prates
Retirada do Último Elemento da Lista
info
prox prox
info
prox
info
NULL
Último
Anterior
NULL
Primeiro
© R. O. Prates
Retirada do elemento após E da Lista
info
prox prox
info
prox
info
NULL
Último
E Primeiro
© R. O. Prates
void RemoveProx(TipoLista *lista, Apontador E){
Apontador tmp;
tmp = E->prox;
if (tmp != NULL) {
E->prox = tmp->prox;
free(tmp);
} else { E->prox = NULL; }
}
tmp
Algoritmos e Estrutura de Dados II
Alocação Encadeada (vantagens e
desvantagens)
n Vantagens:
q Permite inserir ou retirar itens do meio da lista a um custo
constante (importante quando a lista tem de ser mantida em
ordem).
q Bom para aplicações em que não existe previsão sobre o
crescimento da lista (o tamanho máximo da lista não precisa ser
definido a priori).
n Desvantagem:
q Utilização de memória extra para armazenar os apontadores.
q O(n) para acessar um item no pior caso
Algoritmos e Estrutura de Dados II
Exemplo: Ordenação
n Problema: Ordenar uma lista com alocação encadeada em
tempo linear. Esta lista apresenta chaves inteiras com valores
entre 0 e 255.
1
dados1
prox
0
dados2
prox
241
dados3
prox
0
dados4
prox
31
dados5
NULL
. . .
Último Primeiro
Exemplo: Ordenação
n Solução: Criar um vetor com 256 posições contendo
ponteiros para listas com alocação dinâmica.
…
0
255
Lista 0
Lista 255
. . .
Exemplo: Ordenação
n Solução: Criar um vetor com 256 posições contendo
ponteiros para listas com alocação dinâmica.
…
0
255
0
dados
prox
Lista 0
Lista 255
0
dados
prox
. . .
. . .
0
dados
NULL
255
dados
prox
255
dados
prox
. . .
255
dados
NULL
Exemplo: Ordenação
n Ordenação:
n Percorrer lista original
n Utilizar a chave de cada elemento para indexar o vetor
n Insere elemento como último elemento da l ista
correspondente
n Cria uma nova lista com alocação dinâmica
n Percorrer cada elemento do vetor em ordem sequencial
n Percorre cada item da lista correspondente
n Insere item na nova lista
Exemplo: Crivo de Eratóstenes
© R. O. Prates
• Crie uma lista com números de 2 até n.
• Encontre o primeiro número da lista.
• Remova da lista todos os múltiplos do
número primo encontrado.
• O próximo número da lista é primo.
• Repita o procedimento.
• Ao final, a lista contém somente
números primos.
Exercícios
n Implemente uma função que, dada uma lista
encadeada e uma determinada chave C,
remove o elemento com essa chave
n Implemente uma função que remova todos
os elementos de valor par de uma lista
encadeada
© R. O. Prates
AEDSII_aula_013_pilhas_e_filas.pdf
Pilhas e Filas
Algoritmos e Estrutura de Dados II
Listas, Pilhas e Filas
n Listas:
Inserção: em qualquer posição
Remoção: em qualquer posição
n Pilhas:
Inserção: Topo (primeira posição na lista)
Remoção: Topo (primeira posição na lista)
n Filas:
Inserção: Trás (última posição na lista)
Remoção: Início (primeira posição na lista)
Algoritmos e Estrutura de Dados II
TAD Pilhas
n Tipo Abstrato de dados com a seguinte
característica:
O último elemento a ser inserido é o
primeiro a ser retirado
(LIFO – Last In First Out)
n Analogia: pilha de pratos, livros, etc
n Usos: Chamada de subprogramas, avaliação
de expressões aritméticas, etc...
Algoritmos e Estrutura de Dados II
TAD Pilhas
n Conjunto de operações:
1) FPVazia(Pilha). Faz a pilha ficar vazia.
2) Vazia(Pilha). Retorna true se a pilha está vazia;
caso contrário, retorna false.
3) Empilha(x, Pilha). Insere o item x no topo da pilha.
4) Desempilha(Pilha). Retorna o item x no topo da
pilha, retirando-o da pilha.
5) Tamanho(Pilha). Esta função retorna o número de
itens da pilha.
n Representações comuns
n Alocação sequencial (arranjos) e apontadores
Algoritmos e Estrutura de Dados II
TAD Pilhas
M
ax
Ta
m
Topo
Pilha
Empilha(1, Pilha)
Desempilha(1, Pilha)
Topo
Pilha
Algoritmos e Estrutura de Dados II
Implementação de Pilhas com
alocação Sequencial
n Os itens da pilha são armazenados em
posições contíguas de memória.
n Inserções e retiradas: apenas no topo.
n Variável Topo é utilizada para controlar a
posição do item no topo da pilha.
Algoritmos e Estrutura de Dados II
Implementação de Pilhas com
alocação Sequencial
Topo
Pilha
Empilha(21, Pilha) Desempilha(Pilha)
21
Topo
Pilha
Empilha(3, Pilha)
21
3
Topo
Pilha
21
Topo
Pilha
retorna 3
.
Algoritmos e Estrutura de Dados II
Estrutura de Dados de Pilhas com
alocação Sequencial
#define MaxTam 1000
typedef int Apontador;
typedef int TipoChave;
typedef struct {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct {
TipoItem Item[MaxTam];
Apontador Topo;
} TipoPilha;
Item[0]
Item[1]
Item[2]
Item[3]
...
Item[MaxTam-1]
Topo
Pilha
MaxTam
Algoritmos e Estrutura de Dados II
Operações sobre Pilhas com
alocação Sequencial
void FPVazia(TipoPilha *Pilha)
{
Pilha->Topo = 0;
} /* FPVazia */
int Vazia(TipoPilha *Pilha)
{
return (Pilha->Topo == 0);
} /* Vazia */
Operações sobre Pilhas com
alocação Sequencial
void Empilha(TipoItem x, TipoPilha *Pilha)
{
if (Pilha->Topo == MaxTam)
printf(“Erro: pilha está cheia\n");
else {
Pilha->Item[Pilha->Topo] = x;
Pilha->Topo++;
}
}
Topo x Topo x
Topo
Operações sobre Pilhas com
alocação Sequencial
TipoItem Desempilha(TipoPilha *Pilha)
{
if (Vazia(Pilha))
printf(“Erro: a pilha está vazia\n");
else {
Pilha->Topo--;
return Pilha->Item[Pilha->Topo];
}
}
x
Topo
x Topo Topo
Algoritmos e Estrutura de Dados II
Operações sobre Pilhas Usando
Arranjos
int Tamanho(TipoPilha *Pilha)
{
return Pilha->Topo;
}
Algoritmos e Estrutura de Dados II
Implementação de Pilhas por meio de
Apontadores
n Há uma célula cabeça no topo para
facilitar a implementação das operações
empilha e desempilha quando a pilha está
vazia.
n Desempilha: desliga a célula cabeça da
lista a próxima célula, que contém o
primeiro item, passa a ser a célula cabeça.
n Empilha: Cria uma nova célula cabeça e
adiciona o item a ser empilhado na antiga
célula cabeça.
NULL
Algoritmos e Estrutura de Dados II
Estrutura da Pilha Usando
Apontadores
Algoritmos e Estrutura de Dados II
Estrutura da Pilha Usando
Apontadores
typedef int TipoChave;
typedef struct {
int Chave;
/* --- outros componentes --- */
} TipoItem;
typedef struct Celula *Apontador;
typedef struct Celula {
TipoItem Item;
Apontador Prox;
} Celula;
typedef struct {
Apontador Fundo, Topo;
int Tamanho;
} TipoPilha; Fundo
Topo
TipoPilha
Prox
Celula
Prox
Item
Celula
.
Cabeça
Algoritmos e Estrutura de Dados II
Operações sobre Pilhas Usando
Apontadores
void FPVazia(TipoPilha *Pilha)
{
Pilha->Topo = (Apontador) malloc(sizeof(Celula));
Pilha->Fundo = Pilha->Topo;
Pilha->Topo->Prox = NULL;
Pilha->Tamanho = 0;
} /* FPVazia */
Fundo
Topo
TipoPilha
NULL
Prox
Celula
.
Algoritmos e Estrutura de Dados II
Operações sobre Pilhas Usando
Apontadores
int Vazia(TipoPilha *Pilha)
{
return (Pilha->Topo == Pilha->Fundo);
} /* Vazia */
Operações sobre Pilhas Usando
Apontadores
void Empilha(TipoItem x, TipoPilha *Pilha) {
Apontador Aux;
Aux = (Apontador) malloc(sizeof(Celula));
Pilha->Topo->Item = x;
Aux->Prox = Pilha->Topo;
Pilha->Topo = Aux;
Pilha->Tamanho++;
}
Fundo
Topo
TipoPilha
NULL
Prox
Celula
Prox
Celula
Aux
Operações sobre Pilhas Usando
Apontadores
void Empilha(TipoItem x, TipoPilha *Pilha) {
Apontador Aux;
Aux = (Apontador) malloc(sizeof(Celula));
Pilha->Topo->Item = x;
Aux->Prox = Pilha->Topo;
Pilha->Topo = Aux;
Pilha->Tamanho++;
}
Fundo
Topo
TipoPilha
x
NULL
Prox
Celula
Prox
Celula
Aux
Operações sobre Pilhas Usando
Apontadores
TipoItem Desempilha(TipoPilha *Pilha){
Apontador q;
if (Vazia(Pilha)) {
printf(“Erro: pilha vazia\n"); ERRO;
}
q = Pilha->Topo;
Pilha->Topo = q->Prox;
free(q);
Pilha->Tamanho--;
return Topo->Item;
}
Fundo
Topo
TipoPilha
x
NULL
Prox
Celula
Prox
Celula
q
q
Operações sobre Pilhas Usando
Apontadores
TipoItem Desempilha(TipoPilha *Pilha){
Apontador q;
if (Vazia(Pilha)) {
printf(“Erro: pilha vazia\n"); ERRO;
}
q = Pilha->Topo;
Pilha->Topo = q->Prox;
free(q);
Pilha->Tamanho--;
return Topo->Item;
}
Fundo
Topo
TipoPilha
x
NULL
Prox
Celula
Prox
Celula
q
q
Operações sobre Pilhas Usando
Apontadores
TipoItem Desempilha(TipoPilha *Pilha){
Apontador q;
if (Vazia(Pilha)) {
printf(“Erro: pilha vazia\n"); ERRO;
}
q = Pilha->Topo;
Pilha->Topo = q->Prox;
free(q);
Pilha->Tamanho--;
return Topo->Item;
}
Fundo
Topo
TipoPilha
x
NULL
Prox
Celula
q
Algoritmos e Estrutura de Dados II
Operações sobre Pilhas Usando
Apontadores
int Tamanho(TipoPilha *Pilha)
{
return (Pilha->Tamanho);
} /* Tamanho */
Exemplos: Pilhas
Inversão de strings
n Inverter a string “Exemplo” usando uma pilha.
1. Empilha cada caractere em uma pilha vazia
2. Desempilha todos elementos
a
E
E X
E X E
E X E M
E X E M P
E X E M P L
E X E M P L O
E X E M P L O
E X E M P L
E X E M P
E X E M
E X E
E X
E
Exemplos: Pilhas
Conversão notação infixada p/ pós-fixada
n Infixada: (5 * (((9+8) * (4*6)) + 7))
n Pós-fixada: 5 9 8 + 4 6 * * 7 + * (tão logo encontre
um operador, efetua a operação)
n Utilizar uma pilha para converter de infixada para pós-fixada.
a
Converte(char *exp, TipoPilha *pilha){
for (i = 0; i < N; i++) {
if (exp[i] == ‘)’)
printf(“%c “, desempilha(pilha))
if (exp[i] == ‘+’ || exp[i] == ‘*’)
empilha(exp[i], pilha);
if (exp[i] >= ‘0’ && exp[i] <= ‘9’)
printf(“%c “, exp[i]);
}
typedef char TipoItem;
Exemplos: Pilhas
Conversão notação infixada p/ pós-fixada
n entrada: (5 * (((9+8) * (4*6)) + 7))
saída: 5 9 8 + 4 6 * * 7 + * a
Entrada Pilha saída
(
5 5
* *
(((
9 9
+ * +
8 8
) * +
* * *
(
4 4
* * * *
6 6
) * * *
) * *
+ * +
7 7
) * +
) *
Algoritmos e Estrutura de Dados II
TAD Filas
n Tipo Abstrato de dados com a seguinte
característica:
O primeiro elemento a ser inserido é o
primeiro a ser retirado
(FIFO – First In First Out)
n Analogia: fila bancária, fila do cinema
n Usos: Sistemas operacionais: fila de impressão,
processamento
Algoritmos e Estrutura de Dados II
TAD Filas
n Conjunto de operações:
1) FFVazia(Fila). Faz a fila ficar vazia.
2) Enfileira(x, Fila). Insere o item x no final da fila.
3) Desenfileira(Fila). Retorna o item x no início da fila,
retirando-o da fila.
4) Vazia(Fila). Esta função retorna true se a fila está
vazia; senão retorna false.
Algoritmos e Estrutura de Dados II
Implementação de Filas com alocação
sequencial
Arranjos
n Os itens são armazenados em posições contíguas
de memória.
n Enfileira: faz a parte de trás da fila expandir-se.
n Desenfileira: faz a parte da frente da fila contrair-
se.
n A fila tende a se movimentar pela memória do
computador, ocupando espaço na parte de trás e
descartando espaço na parte da frente.
Algoritmos e Estrutura de Dados II
Implementação de Filas com alocação
sequencial
n Com poucas inserções e retiradas, a fila vai ao
encontro do limite do espaço da memória alocado
para ela.
n Solução: imaginar o array como um círculo. A
primeira posição segue a última. .
Implementação de Filas com alocação
sequencial
n A fila se encontra em posições contíguas de memória, em
alguma posição do círculo, delimitada pelos apontadores
Frente e Trás. (Frente: posição do primeiro elemento, trás: a
primeira posição vazia)
n Enfileirar: mover o apontador Trás uma posição no sentido
horário.
n Desenfileirar: mover o apontador Frente uma posição no
sentido horário.
frente
trás
Enfileira(x):
frente
trás
x
Algoritmos e Estrutura de Dados II
Estrutura da Fila com Alocação Sequencial
#define MaxTam 1000
typedef int Apontador;
typedef int TipoChave;
typedef struct {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct {
TipoItem Item[MaxTam];
Apontador Frente, Tras;
} TipoFila;
MaxTam-1
trás
frente
Operações sobre Filas com Alocação
Sequencial
n Nos casos de fila cheia e fila vazia, os apontadores Frente e
Trás apontam para a mesma posição do círculo.
n Uma saída para distinguir as duas situações é deixar uma
posição vazia no array.
n Neste caso, a fila está cheia quando Trás+1 for igual a Frente.
void FFVazia(TipoFila *Fila)
{
Fila->Frente = 0;
Fila->Tras = Fila->Frente;
} /* FFVazia */
int Vazia(TipoFila *Fila)
{
return (Fila->Frente == Fila->Tras);
} /* Vazia */
Operações sobre Filas com Alocação
Sequencial
int Enfileira(TipoItem x, TipoFila *Fila) {
if ((Fila->Tras + 1) % MaxTam == Fila->Frente){
printf("Erro: fila está cheia\n"); return 0;
}
else {
Fila->Item[Fila->Tras] = x;
Fila->Tras = (Fila->Tras + 1) % MaxTam;
}
return 1;
}
MaxTam-1
trás frente
MaxTam-1
trás frente
Operações sobre Filas com Alocação
Sequencial
TipoItem Desenfileira(TipoFila *Fila) {
if (Vazia(Fila)){
printf("Erro: fila está vazia\n"); ERRO;
}
else {
int idx = Fila->Frente;
Fila->Frente = (Fila->Frente + 1) % MaxTam;
return Fila->Item[idx];
}
}
MaxTam-1
frente trás
MaxTam-1
frente trás
Algoritmos e Estrutura de Dados II
Implementação de Filas por meio de
Apontadores
n Utiliza célula cabeça para facilitar a implementação das
operações Enfileira e Desenfileira quando a fila está vazia.
n Quando vazia: apontadores Frente e Trás apontam para a
célula cabeça.
n Enfileirar novo item: criar
uma célula nova, ligá-la após a
célula contendo xn e colocar nela o novo item.
n Desenfileirar: desligar a célula cabeça da lista e a célula que
contém x1 passa a ser a célula cabeça.
NULL
Estrutura da Fila Usando Apontadores
typedef int TipoChave;
typedef struct TipoItem {
TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct Celula *Apontador;
typedef struct Celula {
TipoItem Item;
Apontador Prox;
} Celula;
typedef struct TipoFila {
Apontador Frente, Tras;
} TipoFila;
n A fila é implementada por meio
de células.
n Cada célula contém um item da
fila e um apontador para outra
célula.
n A estrutura TipoFila contém um
apontador para a frente da fila
(célula cabeça) e um apontador
para a parte de trás da fila.
Tras
Frente
TipoFila
Prox
Celula
Prox
Item
Celula
Cabeça
Algoritmos e Estrutura de Dados II
Operações sobre Filas Usando
Apontadores
void FFVazia(TipoFila *Fila)
{
Fila->Frente = (Apontador) malloc(sizeof(Celula));
Fila->Tras = Fila->Frente;
Fila->Frente->Prox = NULL;
} /* FFVazia */
int Vazia(TipoFila *Fila)
{
return (Fila->Frente == Fila->Tras);
} /* Vazia */
Tras
Frente
TipoFila
NULL
Prox
Celula
Operações sobre Filas Usando
Apontadores
void Enfileira(TipoItem x, TipoFila *Fila)
{
Fila->Tras->Prox = (Apontador) malloc(sizeof(Celula));
Fila->Tras = Fila->Tras->Prox;
Fila->Tras->Item = x;
Fila->Tras->Prox = NULL;
}
Tras
Frente
TipoFila
NULL
Prox
Celula
NULL
Prox
x
Celula
Operações sobre Filas Usando
Apontadores
TipoItem Desenfileira(TipoFila *Fila){
Apontador q;
if (Vazia(Fila)) {
printf("Erro: fila está vazia\n"); ERRO;
}
q = Fila->Frente;
Fila->Frente = Fila->Frente->Prox;
free(q);
return Fila->Frente->Item;
}
Trás
Frente
TipoFila
x
NULL
Prox
Celula
Prox
Celula
AEDSII_aula_014_arvores.pdf
¡ Organizam
dados
de
forma
hierárquica
¡ Acontecem
com
frequência
na
natureza
¡ Fáceis
de
representar
e
manipular
com
computadores
¡ Úteis
para
várias
tarefas
Raiz
Folhas
Nós
internos
Filhos
Pai
Descendentes
Ancestrais
Irmãos
Níveis
0
1
2
3
4
Caminho
¡ Árvores
não
contêm
ciclos
§ Só
existe
um
caminho
entre
qualquer
par
de
nós
¡ Qualquer
árvore
pode
ser
transformada
numa
árvore
binária
§ Focaremos
em
árvores
binárias
pois
elas
são
mais
fáceis
de
armazenar
e
manipular
¡ Uma
árvore
binária
é
uma
árvore
com
zero,
um
ou
dois
filhos
onde
cada
filho
é
também
uma
árvore
binária
§ Definição
é
recursiva
§ Veremos
que
manipulação
de
árvores
é
fácil
usando
recursão
struct arvore {
struct arvore *esq;
struct arvore *dir;
int dado;
};
¡ Pré-‐ordem
¡ Ordem
central
¡ Pós-‐ordem
3 2
1
3 1
2
2 1
3
void pre_ordem(struct arvore *f) {
if(f == NULL) {
return;
}
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1 2
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1 2 4
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1 1 2 4 7
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1 2 4 7 A
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1 2 4 7 A B
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1 2 4 7 A B 3
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
1 2 4 7 A B 3 5 6 8 C 9
void pre_ordem(struct arvore *f){
if(f == NULL) { return; }
printf(“%d”, f->dado);
pre_ordem(f->esq);
pre_ordem(f->dir);
}
void ordem_central(struct arvore *f)
{
if(f == NULL) { return; }
ordem_central(f->esq);
printf(“%d”, f->dado);
ordem_central(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
A
void ordem_central(struct arvore *f){
if(f == NULL) { return; }
ordem_central(f->esq);
printf(“%d”, f->dado);
ordem_central(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
A 7
void ordem_central(struct arvore *f){
if(f == NULL) { return; }
ordem_central(f->esq);
printf(“%d”, f->dado);
ordem_central(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
A 7 B
void ordem_central(struct arvore *f){
if(f == NULL) { return; }
ordem_central(f->esq);
printf(“%d”, f->dado);
ordem_central(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
A 7 B 4
void ordem_central(struct arvore *f){
if(f == NULL) { return; }
ordem_central(f->esq);
printf(“%d”, f->dado);
ordem_central(f->dir);
}
3 2
1
4 6
7 8 9
A B C
5
A 7 B 4 2 1 5 3 C 8 6 9
void ordem_central(struct arvore *f){
if(f == NULL) { return; }
ordem_central(f->esq);
printf(“%d”, f->dado);
ordem_central(f->dir);
}
void pos_ordem(struct arvore *f)
{
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
A
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
3 2
1
4 6
7 8 9
A B C
5
2
1
4
7
A
A B
3 2
1
4 6
7 8
A B C
5
9
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
A B 7
3 2
1
4 6
7 8
A B C
5
9
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
A B 7 4
3 2
1
4 6
7 8
A B C
5
9
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
A B 7 4 2
3 2
1
4 6
7 8
A B C
5
9
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
A B 7 4 2 5
3 2
1
4 6
7 8
A B C
5
9
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
A B 7 4 2 5 C
3 2
1
4 6
7 8
A B C
5
9
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
A B 7 4 2 5 C 8 9 6 3 1
3 2
1
4 6
7 8
A B C
5
9
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
5 9 8 + 4 6 * * 7 + *
+5
*
7
+ *
9 8 4
*
6
void pos_ordem(struct arvore *f){
if(f == NULL) { return; }
pos_ordem(f->esq);
pos_ordem(f->dir);
printf(“%d”, f->dado);
}
¡ Até
agora
consideramos
árvores
que
organizam
os
dados
em
forma
hierárquica
sem
inspecionar
os
elementos
¡ Árvores
de
busca
mantém
uma
ordem
entre
seus
elementos
§ Raiz
é
maior
que
os
elementos
na
árvore
à
esquerda
§ Raiz
é
menor
que
os
elementos
na
árvore
à
direita
8 5
6
4 B
2 A C
1 3 9
7
0
struct arvore {
struct arvore *esq;
struct arvore *dir;
int dado;
};
struct arvore * cria_arvore(void) {
struct arvore *novo;
novo = malloc(sizeof(struct arvore));
novo->esq = NULL;
novo->dir = NULL;
novo->dado = 0;
}
struct arvore *busca_elemento(struct arvore *t, int D) {
if(t == NULL) /* elemento não existente na árvore */
return NULL;
else if (D == t->dado) /* encontrou elemento */
return t;
else if (D < t->dado) /* busca na árvore esquerda */
return busca_elemento(t->esq, D);
else if (D > t->dado) /* busca na árvore direita */
return busca_elemento(t->dir, D);
}
void acha_menor(arvore *t) {
if(t->esq == NULL) {
return t;
}
return acha_menor(t->esq);
}
¡ O
elemento
vai
ser
inserido
como
uma
folha
da
árvore
de
busca
¡ Vamos
procurar
o
lugar
de
inserção
navegando
da
raiz
até
a
folha
onde
ele
será
inserido
8 5
6
4 B
2 A C
1 3 9
7
4.5
8 5
6
4 B
2 A C
1 3 9
7
4.5
8 5
6
4 B
2 A C
1 3 9
7 4.5
8 5
6
4 B
2 A C
1 3 9
7
4.5
void insere_elemento(struct arvore *t, int D) {
if(D < t->dado) {
if(t->esq) { insere_elemento(t->esq, D); }
else { /* achou local de inserção */
struct arvore *novo = cria_arvore();
novo->dado = D;
t->esq = novo;
}
} else if(D > t->dado) {
if(t->dir) { insere_elemento(t->dir, D); }
else {
struct arvore *novo = cria_arvore();
novo->dado = D;
t->dir = novo;
}
} else {
printf(“elemento já existe na árvore\n”);
}
}
¡ Remover
folhas
¡ Remover
nós
com
um
filho
¡ Remover
nós
com
dois
filhos
8 5
6
4 B
2 A C
1 3 9
7
8 5
6
4 B
2 A C
1 3 9
7
8 5
6
B2
A C1 3
9
7
8 5
6
4 B
2 A C
1 3 9
7
sucessor
8 5
7
4 B
2 A C
1 3 9
7
8 5
7
4 B
2 A C
1 3 9
7
struct arvore *remove(struct arvore *t, int D) {
struct arvore *aux;
if(t == NULL) { printf(“elemento ausente\n”); }
else if(D < t->dado){ t->esq = remove(t->esq, D);}
else if(D > t->dado){ t->dir = remove(t->dir, D);}
else if(t->esq == NULL && t->dir == NULL) {
free(t); return NULL; /* zero filhos */
}
else if(t->esq == NULL) {
aux = t->dir; free(t); return aux; /* 1 filho */
}
else if(t->dir == NULL) {
aux = t->esq; free(t); return aux; /* 1 filho */
} else { /* 2 filhos */
struct arvore *suc = acha_menor(t->dir);
t->dado = suc->dado;
t->dir = remove(t->dir, suc->dado);
return t;
}
return t;
}
void acha_menor(arvore *t) {
if(t->esq == NULL) {
return t;
}
return acha_menor(t->esq);
}
AEDSII_aula_015_ordenacao.pdf
Ordenação: Introdução e
métodos elementares
Algoritmos e Estruturas de Dados II
Ordenação
} Objetivo:
} Rearranjar os itens de um vetor ou lista de modo que suas
chaves estejam ordenadas de acordo com alguma regra.
} Estrutura:
typedef int TipoChave;
typedef struct {
ChaveTipo chave;
/* outros componentes */
} Item;
2
E X E M P L O E E L M O P X
Critérios de Classificação
} Localização dos dados:
} Ordenação interna: todas as chaves estão na memória
principal.
} Ordenação externa: chaves na memória principal e na
memória secundária.
} Estabilidade:
} Relacionado com o manutenção da ordem relativa entre
chaves de mesmo valor.
} Método é estável se a ordem relativa dos registros com a
mesma chave não se altera após a ordenação.
3
E X E M P L O E E L M O P X
1 1 2 2
Critérios de Classificação
} Uso da memória:
} In place: transforma os dados de entrada utilizando apenas
um espaço extra de tamanho constante.
} Movimentação dos dados:
} Direta: registro todo é acessado e deve ser movido
} Indireta: apenas as chaves são acessadas e ponteiros são
rearranjados e não o registro todo.
} Adaptabilidade:
} Sequência de operações executadas conforme a entrada.
} Não adaptável: operações executadas independe da entrada.
4
Critérios de Avaliação
5
} Seja n o número de registros em um vetor, considera-
se duas medidas de complexidade:
} Número de comparações C(n) entre as chaves;
} Número de trocas ou movimentações M(n) de itens;
#define Troca(A, B) {Item c = A; A = B; B = c; }
void Ordena(Item *v, int n) {
int i, j;
for (i = 0; i < n-1; i++) {
for (j = n-1; j > i; j--) {
if (v[j-1].chave > v[j].chave) /* comparações */
Troca(v[j-1], v[j]); /* trocas */
}
Método Bolha
6
} Ideia:
} Passa no arquivo e troca elementos adjacentes que estão
fora de ordem, até os registros ficarem ordenados.
} Algoritmo
} Supondo movimentação da esquerda para direita no vetor;
} Quando o maior elemento do vetor for encontrado, ele será
trocado até ocupar a última posição;
} Na segunda passada, o segundo maior será movido para a
penúltima posição do vetor.
E X E M P L O
E E X M P L O
E E M X P L O
E E M P X L O
E E M P L X O
E E M P L O X
E E M P L O X
Método Bolha
7
void Bolha (Item *v, int n) {
int i, j;
for(i = 0; i < n-1; i++)
for(j = 1; j < n-i; j++)
if (v[j].chave < v[j-1].chave)
Troca(v[j-1], v[j]);
}
Método Bolha
8
void Bolha (Item *v, int n) {
int i, j;
for(i = 0; i < n-1; i++)
for(j = 1; j < n-i; j++)
if (v[j].chave < v[j-1].chave)
Troca(v[j-1], v[j]);
}
E X E M P L O
E E M P L O X
E E M L O P X
E E L M O P X
E E L M O P X
E E L M O P X
E E L M O P X
E E L M O P X
Método Bolha: Complexidade
9
} Comparações – C(n):
void Bolha (Item *v, int n) {
int i, j;
for(i = 0; i < n-1; i++)
for(j = 1; j < n-i; j++)
if (v[j].chave < v[j-1].chave)
Troca(v[j-1], v[j]);
}
}
)n(Onn
)n()n)(n()n(n
in)in()n(C
n
i
n
i
n
i
n
i
n
i
in
j
2
2
2
0
2
0
2
0
2
0
2
0 1
2
12
2
211
111
=
−
=
+−−
−−
−−=
−−=−−== ∑ ∑∑∑∑∑
−
=
−
=
−
=
−
=
−
=
−
=
Método Bolha: Complexidade
10
} Movimentações – M(n):
)n(C)n(M =
#define Troca(A, B) {Item c = A; A = B; B = c; }
Método Bolha
11
} Vantagens
} Algoritmo simples
} Algoritmo estável
} Desvantagens
} Não adaptável
} Muitas trocas de itens
Variação Bolha: Ordenação Par-Ímpar
12
void ParImpar(Item *v, int n) {
int ordenado = 0;
while(!ordenado) {
ordenado = 1;
for(int i = 0; i < n-1; i += 2)
if(v[i] > v[i+1]) {
Troca(v[i], v[i+1]);
ordenado = 0;
}
for (int i = 1; i < n-1; i += 2)
if(v[i] > v[i+1]) {
Troca(v[i], v[i+1]);
ordenado = 0;
}
}
Método Seleção
13
} Seleção do n-ésimo menor (ou maior) elemento da
lista
} Troca do n-ésimo menor (ou maior) elemento com a
n-ésima posição da lista
} Uma única troca por vez é realizada
Método Seleção
14
void Selecao (Item *v, int n){
int i, j, Min;
for (i = 0; i < n - 1; i++) {
Min = i;
for (j = i + 1 ; j < n; j++)
if (v[j].chave < v[Min].chave)
Min = j;
Troca(v[i], v[Min]);
}
}
E X E M P L O
E X E M P L O
E E X M P L O
E E L M P X O
E E L M P X O
E E L M O X P
E E L M O P X
E E L M O P X
Método Seleção: Complexidade
15
} Comparações – C(n):
} Movimentações – M(n):
)n(Onn
)n()n)(n()n(n
in)i()n()n(C
n
i
n
i
n
i
n
i
2
2
2
0
2
0
2
0
2
0
2
1
2
211
1111
=
−
=
−−
−−
−−=
−−=+++−= ∑∑∑∑
−
=
−
=
−
=
−
=
)n(O)n()n(M =−= 1
Método Seleção
16
} Vantagens:
} Custo linear no tamanho da entrada para o número de
movimentos de registros – a ser utilizado quando há
registros muito grandes;
} Desvantagens:
} Não adaptável (não importa se o arquivo está parcialmente
ordenado);
} Algoritmo não é estável;
Método Inserção
17
} Algoritmo utilizado pelo jogador de cartas
} As cartas são ordenadas da esquerda para direita uma a
uma.
} O jogador escolhe a segunda carta e verifica se ela deve
ficar antes ou na posição que está.
} Depois a terceira carta é classificada, deslocando-a até sua
correta posição.
} O jogador realiza esse procedimento até ordenar todas as
cartas.
Método Inserção
18
Método Inserção
19
void Insercao(Item *v, int n) {
int i,j;
Item aux;
for (i = 1; i < n; i++) {
aux = v[i];
j = i - 1;
while (( j >= 0 ) && (aux.Chave < v[j].Chave)) {
v[j + 1] = v[j];
j--;
}
v[j + 1] = aux;
}
}
E X E M P L O
E X E M P L O
E E X M P L O
E E M X P L O
E E M P X L O
E E L M P X O
E E L M O P X
Método Inserção: Complexidade
20
} Comparações – C(n):
} Anel interno: i-ésima iteração, valor de Ci:
} melhor caso: Ci = 1
} pior caso: Ci = i
} caso médio: Ci = (1 + 2 + 3 + ... + i) / i
} Para o caso médio, assume-se que todas as permutações de
entrada são igualmente prováveis.
2
1
2
)1(11
1
+
=⎟
⎠
⎞
⎜
⎝
⎛ +== ∑
=
iii
i
k
i
C
i
k
i
Método Inserção: Complexidade
21
} Comparações – C(n):
} Anel externo:
} Complexidade total:
} Melhor caso (itens já estão ordenados)
} Pior caso (itens em ordem reversa):
∑
−
=
1
1
n
i
iC
∑
−
=
=−==
1
1
)(11)(
n
i
nOnnC
)(
222
))(1()( 2
1
1
2
nOnnnninC
n
i
=−=
−
==∑
−
=
Método Inserção: Complexidade
22
} Comparações – C(n):
} Caso médio:
⎟
⎠
⎞
⎜
⎝
⎛ −+
−
=⎟
⎠
⎞
⎜
⎝
⎛
+=
+
=∑ ∑∑
−
=
−
=
−
=
)1(
2
)1(
2
11
2
1
2
1)(
1
1
1
1
1
1
nnniinC
n
i
n
i
n
i
)(
2
1
442
1
4
2
22
nOnnnnn =−+=⎟⎟
⎠
⎞
⎜
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛ −+⎟⎟
⎠
⎞
⎜⎜
⎝
⎛ −
=
Método Inserção: Exemplos
23
} Melhor Caso:
} Pior Caso:
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
6 5 4 3 2 1
5 6 4 3 2 1
4 5 6 3 2 1
3 4 5 6 2 1
2 3 4 5 6 1
1 2 3 4 5 6
Método Inserção
24
} Vantagens:
} É o método a ser utilizado quando o arquivo está “quase”
ordenado.
} É um bom método quando se deseja adicionar uns poucos
itens a um arquivo ordenado, pois o custo é linear.
} O algoritmo de ordenação por inserção é estável.
} Desvantagens:
} Alto custo de movimentação de elementos no vetor.
Ordenação Interna: Sumário
25
} Métodos Simples:
} Adequados para pequenos arquivos.
} Requerem O(n2) comparações.
} Produzem programas pequenos.
} Métodos Eficientes:
} Adequados para arquivos maiores.
} Requerem O(n log n) comparações.
} As comparações são mais complexas nos detalhes.
} Métodos simples são mais eficientes para pequenos
arquivos.
Perguntas
26
} Como adicionar estabilidade: Sedgewick p. 259
AEDSII_aula_016_shellsort.pdf
Ordenação: Shellsort
Algoritmos e Estruturas de Dados II
Introdução
} Proposto por Donald Shell em 1959.
} Extensão do algoritmo de ordenação inserção.
2
Motivação
3
while (( j >= 0 ) && (aux.Chave < v[j].Chave)) {
v[j
+ 1] = v[j];
j--;
}
11 comp.
24 comp.
Motivação
4
} Problema do método de inserção
} Troca itens adjacentes para determinar o ponto de inserção.
} São efetuadas n - 1 comparações e movimentações quando
o menor item está na posição mais à direita no vetor.
} O método de Shell contorna este problema
permitindo trocas de registros distantes um do outro.
Algoritmo
5
} Os itens separados de h posições são rearranjados.
} Todo h-ésimo item leva a uma sequência ordenada.
} Tal sequência é dita estar h-ordenada.
} Quando h=1, o algoritmo é equivalente ao algoritmo
de inserção
Exemplo
6
} Entrada: O R D E N A
} h = 4, 2, 1
Escolha do h
7
} Sequência para h:
} A sequência corresponde a 1, 4, 13, 40, 121, 364,
1093, 3280, ...
} Knuth (1973, p. 95) mostrou experimentalmente que
esta sequência é difícil de ser batida por mais de 20%
em eficiência.
1s para 113
1 s para ,1)(
>+=
==
)h(s- h(s)
sh
ShellSort
void Shellsort (Item* A, int n) {
int i, j;
int h = 1;
Item aux;
do /* calcula o h inicial */
h = h * 3 + 1;
while (h < n);
do {
h = (h-1/3); /* atualiza o valor de h */
for(i = h; i < n; i++) {
aux = A[i]; j = i;
/* efetua comparações entre elementos com distância h */
while (A[j – h].Chave > aux.Chave) {
A[j] = A[j – h]; j -= h;
if (j < h) break;
}
A[j] = aux;
}
} while (h != 1);
}
ShellSort
n Análise
q A razão da eficiência do algoritmo ainda não é
conhecida.
q Ninguém ainda foi capaz de analisar o algoritmo.
q A sua análise contém alguns problemas
matemáticos muito difíceis.
q A começar pela própria seqüência de incrementos.
q O que se sabe é que cada incremento não deve ser
múltiplo do anterior.
ShellSort
n Análise
q Conjecturas referente ao número de
comparações para a seqüência de Knuth:
Conjectura 1 : C(n) = O(n1,25)
Conjectura 2 : C(n) = O(n (ln n)2 )
ShellSort
n Vantagens:
q Shellsort é uma ótima opção para arquivos de tamanho
moderado.
q Sua implementação é simples e requer uma quantidade de
código pequena.
n Desvantagens:
q O tempo de execução do algoritmo é sensível à ordem
inicial do arquivo.
q O método não é estável.
Exercícios
12
1. Mostre um exemplo de entrada que demonstra que o
método de ordenação seleção não é estável.
2. Mostre um exemplo que demonstra que o Shellsort é
instável para sequencia h=1,2
3. O método da bolha não é adaptável, altere o código para
que ele se torne adaptável.
4. Qual dos métodos: bolha, inserção e seleção executa menos
comparações para um vetor de entrada contendo valores
idênticos.
Exercícios
13
1. Dê um exemplo de um vetor com N elementos que
maximiza o número de vezes que o mínimo é atualizado no
método de ordenação seleção.
2. Mostre um exemplo de entrada que demonstra que o
método de ordenação seleção não é estável.
3. Mostre um exemplo que demonstra que o Shellsort é
instável para sequencia h=1,2
4. O método da bolha não é adaptável, altere o código para
que ele se torne adaptável.
5. Qual dos métodos: bolha, inserção e seleção executa menos
comparações para um vetor de entrada contendo valores
idênticos.
14
AEDSII_aula_017_quicksort.pdf
Ordenação: Quicksort
Algoritmos e Estruturas de Dados II
Introdução
2
} É o algoritmo de ordenação interna mais rápido que se
conhece para uma ampla variedade de situações.
} Provavelmente é o mais utilizado.
} A ideia básica é dividir o problema de ordenar um conjunto
com n itens em dois problemas menores.
} Os problemas menores são ordenados independentemente.
} Os resultados são combinados para produzir a solução final.
Introdução
3
} A parte mais delicada do método é o processo de
partição.
} O vetor A [Esq ... Dir] é rearranjado por meio da
escolha arbitrária de um pivô x.
} O vetor A é particionado em duas partes:
} Parte esquerda: chaves ≤ x.
} Parte direita: chaves > x.
Exemplo
4
x
Dificuldades na escolha do pivô
5
Algoritmo – Particionamento
6
} Algoritmo para particionamento:
1. Escolha arbitrariamente um pivô x, troque com elemento
mais à direita.
2. Seta p (divisão da partição) para esquerda do vetor
3. Percorre o vetor da esquerda para direita
1. Se elemento A[i] ≤ pivô x
1. Troca A[i] pelo elemento A[p]
2. Incrementa posição da divisão da partição, p
4. Troca pivô da direita para atual divisão da partição
5. Retorna a posição que divide a partição.
Algoritmo – Após Partições
7
} Ao final de cada particionamento, os elementos do
vetor A[esq … dir] estão
} A[esq], A[esq +1], …, A[j]: menores ou iguais a x
} A[i], A[i+1],…,A[dir]: maiores que x
} Uma vez obtidas as partições, cada uma deve ser
ordenada – recursivamente.
≤ x x > x
Particionamento
8
int particiona(Item a[], int e, int d) {
int i, p; /* contém índice da divisão da partição */
Item pivo = a[d];
p = e;
for (i = e; i < d; i++) {
if (a[i].chave <= pivo.chave)
Troca(a[i],a[p++]);
}
Troca(a[p],a[d]);
return p;
}
Particionamento - Exemplo
9
2 8 7 1 3 5 6 4
2 8 7 1 3 5 6 4
i p
2 8 7 1 3 5 6 4
i p
2 8 7 1 3 5 6 4
i p
2 1 7 8 3 5 6 4
i p
2 1 3 8 7 5 6 4
i p
2 1 3 8 7 5 6 4
i p
2 1 3 4 7 5 6 8
Algoritmo – Recursão
10
} Cuidados para que a execução termine
} Não chamar a recursão para apenas um elemento.
} Chamar a recursão para partições menores que a atual.
void ordena(Item a[], int e, int d) {
int i;
if (d < e) return; /* condição de parada */
i = particiona(a, e, d); /* i: índice do pivô */
ordena(a, e, i-1); /* ordena partição esquerda */
ordena(a, i+1, d); /* ordena partição direita */
}
void quicksort(Item a[], int n) {
ordena(a, 0, n-1);
}
Quicksort - Exemplo
} O pivô x é escolhido como sendo A[d].
} Exemplo:
Algoritmos e Estrutura de Dados II
3 6 4 5 1 7 2
Quicksort - Exemplo
Algoritmos e Estrutura de Dados II
3 6 4 5 1 7 2
1 2 4 5 3 7 6
Primeira
partição
1 2 4 3 5 7 6
ordena
1 2 4 5 3 6 7 segunda partição
1 2 4 5 3 7 6
Quicksort - Exemplo
13
1 2 4 5 3 6 7
1 2 4 5 3 6 7
1 2 4 5 3 6 7
ordena
1 2 4 5 3 6 7
terceira
partição
1 2 3 4 5 6 7
Quicksort - Exemplo
14
1 2 3 4 5 6 7
ordena 1 2 3 4 5 6 7
1 2 3 4 5 6 7
quarta
partição
1 2 3 4 5 6 7
1 2 3 4 5 6 7 ordena
1 2 3 4 5 6 7 final
Quicksort
} Características
} Qual o pior caso para o Quicksort? Qual sua ordem de
complexidade?
} Qual o melhor caso?
} O algoritmo é estável?
Algoritmos e Estrutura de Dados II
Quicksort – Análise
16
} Seja C(n) a função que conta o número de comparações.
} Pior caso:
C(n) = O(n2)
} O pior caso ocorre quando, sistematicamente, o pivô é
escolhido como sendo um dos extremos de um arquivo já
ordenado.
} Isto faz com que o procedimento Ordena seja chamado
recursivamente
n vezes, eliminando apenas um item em cada
chamada.
Quicksort – Análise
} Melhor caso:
C(n) = 2C(n/2) + n = O(n log n)
} Esta situação ocorre quando cada partição divide o arquivo
em duas partes iguais.
} Caso médio de acordo com Sedgewick e Flajolet (1996, p.
17):
C(n) ≈ 1,386n log n – 0,846n,
} Isso significa que em média o tempo de execução do
Quicksort é O(n log n).
Algoritmos e Estrutura de Dados
II
Melhorias no Quicksort
} Escolha do pivô: mediana de três
} Evita o pior caso
} Depois da partição, trabalhar primeiro no subvetor
de menor tamanho
} Diminui o crescimento da pilha
} Utilizar um algoritmo simples (seleção, inserção)
para partições de tamanho pequeno
} Quicksort não recursivo
} Evita o custo de várias chamadas recursivas
Quicksort não recursivo
19
void quicksortNR(Item a[], int n) {
int i, e, d;
TipoPilha p;
FPVazia(&p); Empilha(&p, n-1); Empilha(&p, 0);
while (Vazia(&p) == 0) {
e = Desempilha(&p); d = Desempilha(&p);
i = particiona(a, e, d);
/* partição esquerda */
if (i-1 > e) { Empilha(&p, i-1); Empilha(&p, e);}
/* partição direita */
if (d > i+1) { Empilha(&p, d); Empilha(&p, i+1); }
}
Quicksort
Algoritmos e Estrutura de Dados II
} Vantagens:
} É extremamente eficiente para ordenar arquivos de dados.
} Necessita de apenas uma pequena pilha como memória
auxiliar.
} Requer cerca de n log n comparações em média para
ordenar n itens.
} Desvantagens:
} Tem um pior caso O(n2) comparações.
} Sua implementação é muito delicada e difícil:
} Um pequeno engano pode levar a efeitos inesperados para
algumas entradas de dados.
} O método não é estável.
Seleção usando Quicksort
21
} Objetivo
} Encontrar o k-ésimo menor elemento sem ordenar todo o
vetor.
} Algoritmo coloca o elemento ordenado na k-ésima
posição do vetor.
void seleciona(Item a[], int e, int d, int k) {
int i;
if (d <= e) return; /* condição de parada */
i = particiona(a, e, d); /* i: índice do pivô */
if (k < i) seleciona(a, e, i-1,k); /*k-th na esquerda*/
if (k > i) seleciona(a, i+1, d); /* k-th na direita */
}
Exercícios
22
1. Mesmo com o uso da estratégia da mediana, mostre um
vetor de entrada que cai no pior caso do quicksort.
2. Por que não usar o algoritmo de ordenação por seleção
para identificar o k-ésimo menor elemento do vetor?
AEDSII_aula_018_heapsort.pdf
Ordenação: Heapsort
Algoritmos e Estruturas de Dados II
Introdução
2
} Possui o mesmo princípio de funcionamento da
ordenação por seleção.
} Selecione o menor item do vetor
} Troque-o pelo item da primeira posição
} Repita operação com os elementos restantes do vetor
} Implementação direta
} Encontrar o menor elemento requer n-1 comparações
} Ideia:
} Utilização de uma fila de prioridades implementada com um
heap.
Fila de Prioridades
3
} Definição:
} Estrutura de dados composta de chaves, que suporta duas
operações básicas: inserção de um novo item e remoção do
item com a maior chave.
} A chave de cada item reflete a prioridade em que se deve
tratar aquele item.
} Aplicações:
} Sistemas operacionais, sistema de memória (paginação).
Fila de Prioridades
4
} Operações
} Constrói a fila de prioridade com N itens
} Insere um novo item
} Retira o maior item
} Altera a prioridade de um item
Fila de Prioridades
5
} Representações
} Lista sequencial ordenada, não ordenada e heap.
Constrói Insere Retira máximo
Lista ordenada O(N log N) O(N) O(1)
Lista não ordenada O(N) O(1) O(N)
heaps O(N log N) O(log N) O(log N)
Fila de Prioridades
6
} Algoritmos de ordenação com fila de prioridades
} Utiliza operação insere para adicionar todas as N chaves
} Utiliza a operação retira máximo para receber uma lista na
ordem reversa.
Algoritmo
Lista ordenada
Lista não ordenada
heaps
Fila de Prioridades
7
} Algoritmos de ordenação com fila de prioridades
} Utiliza operação insere para adicionar todas as N chaves
} Utiliza a operação retira máximo para receber uma lista na
ordem reversa.
Algoritmo
Lista ordenada Inserção
Lista não ordenada Seleção
heaps Heapsort
Heap
8
} Representação vetorial A[1], A[2], ..., A[n]
} Será um heap se A[i] ≥A[2i] e A[i] ≥ A[2i+1] para todo i
= 1, 2, 3, ..., n/2.
} Representação de árvore binária
} Será um heap se cada nó for maior ou igual seus filhos.
Heap
9
} Representação vetorial para de árvore
} Nós são numerados de 1 a n
} O primeiro é chamado raiz
} O nó k/2 é o pai do nó k, 1 < k ≤ n
} Os nós 2k e 2k+1 são filhos da esquerda e direita do nó k,
para 1 ≤ k ≤ n/2.
Heap
10
} Representação por meio de vetores é compacta
} Permite caminhar pelos nós da árvore facilmente
} Filhos de um nó i estão nas posições 2i e 2i + 1
} O pai de um nó i está na posição i/2
} A maior chave sempre está na posição 1
Heap
11
} Restauração da condição de heap (adição no fim)
} Garantir que o valor da chave do pai é maior que dos filhos.
} Testa se todos os elementos A[2i] e A[2i+1] são menores ou
igual a A[i].
R O D E N A S
1 2 3 4 5 6 7
1 2 3 4 5 6 7
R O D E N A S
R O S E N A D
S O R E N A D
O R D E N A R O D E N A
Heap
12
} Restauração da condição de heap (árvore)
O R D E N A S
1 2 3 4 5 6 7
O
R D
E N A S
1
2 3
6 5 4 7
O
R D
E N A S
1
2 3
6 5 4 7
O
R S
E N A D
1
2 3
6 5 4 7
1 2
3 S
R O
E N A D
1
2 3
6 5 4 7
4
Heap – Refaz a condição de heap
13
void RefazBaixoCima(Item A[], int k) {
/* se pai for menor que filho, troca */
while (k > 1 && A[k/2] < A[k]) {
Troca(A[k], A[k/2]);
/* vai para o pai e repete o processo */
k = k / 2;
}
Heap
14
} Restauração da condição de heap (remoção)
} Garantir que o valor da chave do pai é maior que dos filhos.
Cima para baixo, restaurando o heap
1 2 3 4 5 6 7
S O R E N A D
S O R E N A D
D O R E N A
R O D E N A
Heap – Refaz a condição de heap
15
void RefazCimaBaixo(Item A[], int k, int Dir) {
int j;
while (2*k <= Dir) {
j = 2*k;
/* encontra maior filho */
if (j < Dir && A[j] < A[j+1])
j++;
/* testa se pai é maior que filho */
if (A[k] >= A[j])
break;
/* pai é menor que filho, troca posições */
Troca(A[k], A[j]);
k = j;
}
}
Heap – Construção do heap
16
void Constroi(Item A[], int N) {
int Esq;
/* inicia na metade do vetor */
Esq = N / 2 + 1;
while (Esq > 1) {
Esq--;
RefazCimaBaixo(A, Esq, N);
}
Fila de Prioridade - Operações
17
Int N; /* controla número de elementos na fila */
Item pq[MaxN]; /* contém os dados */
/* inicia fila de prioridade */
Void FPInicia() { N = 0; }
/* insere um elemento */
void FPInsere(Item v) {
A[++N] = v;
RefazBaixoCima(pq, N);
}
/* remove elemento com valor
máximo */
Item FPRemoveMaximo() {
Troca(pq[1], pq[N]);
RefazCimaBaixo(pq, 1, N-1);
return pq[N--];
}
Ordenação com fila de prioridades
18
Void FPSort(Item A[], int n) {
int k;
FPInicia();
/* insere elementos na fila de prioridade */
for (k = 0; k < n; k++)
FPInsere(A[k]);
/* remove maiores elementos da fila de prioridade */
for (k = n-1; k >= 0; k--)
a[k] = FPRemoveMaximo();
}
Heapsort
19
void Heapsort(Item A[], int n) {
int Esq, Dir;
Item x;
Constroi(A, n); /* constroi o heap */
Esq = 1; Dir = n; /* assumindo elementos em A[1,...,n]*/
/* ordena o vetor */
while (Dir > 1) {
Troca(A[1], A[Dir]);
Dir--;
RefazCimaBaixo(A, Esq, Dir);
}
}
Heapsort – Análise
Algoritmos e Estrutura de Dados II
} O procedimento RefazCimaBaixo gasta cerca de
log n operações no pior caso.
} Logo, o heapsort gasta um tempo proporcional a
O(n log n), no pior caso.
Heapsort
21
} Vantagens
} O(n log n).
} Desvantagens
} Não é estável.
Exercícios
22
1. Por que não usar o algoritmo de ordenação por
seleção para identificar o k-ésimo menor elemento
do vetor?
2. Mesmo com o uso da estratégia da mediana, mostre
um vetor de entrada que cai no pior caso do
quicksort.
3. Um vetor com elementos em ordem reversa é um
heap?
4. Mostre que o heapsort não é estável.
AEDSII_aula_018_mergesort.pdf
Ordenação: Mergesort
Algoritmos e Estruturas de Dados II
Introdução
2
} Baseado em merging
} Combinação de dois vetores ordenados em um vetor maior
que também esteja ordenado
} Quicksort vs. Mergesort
} Quicksort:
} divide o vetor em vetores independentes
} Indexação da posição do pivô + duas chamadas recursivas
} Mergesort:
} une dois vetores para criar um único
} Duas chamadas recursivas + procedimento para unir vetores
Merging
3
} Dois vetores a e b ordenados para um vetor c
} Ideia
} Escolhe para c, o menor de dos elementos que ainda não
foram escolhidos dos vetores a e b.
mergeAB(Item c[], Item a[], int N, Item b[], int M ) {
int i, j, k;
for (i = 0, j = 0, k = 0; k < N+M; k++) {
if (i == N) { c[k] = b[j++]; continue; }
if (j == M) { c[k] = a[i++]; continue; }
if (a[i].chave < b[j].chave)
c[k] = a[i++];
else
c[k] = b[j++];
}
}
Merging
4
} Problema
} Há dois testes no laço interno.
} Dois vetores separados são passados (a e b)
} Solução
} Para evitá-los, copia um dos vetores em ordem reversa e o
percorre da direita para esquerda.
} Passa vetor único, indicando o índice do último elemento do
vetor da esquerda (variável m).
Merging
5
Item aux[maxN];
merge(Item a[], int e, int m, int d){
int i, j, k;
/* copia a e b (reverso) para vetor auxiliar */
for (i = 0; i <= m; i++)
aux[i] = a[i];
for (j = m+1; j <= d; j++)
aux[d-m+j+1] = a[j];
i = e; j = d;
for (k = e; k <= d; k++)
if (aux[i].chave <= aux[j].chave)
a[k] = aux[i++];
else
a[k] = aux[j--];
}
Mergesort
6
void mergesort(Item a[], int e, int d) {
int m = (d+e)/2;
if (d <= e) return;
mergesort(a, e, m);
mergesort(a, m+1, d);
merge(a, e, m, d);
}
Mergesort não Recursivo
7
#define min(A, B) (A < B) ? A : B
void mergesortBU(Item a[], int e, int d) {
int i, m;
for (m = 1; m < d-e; m = m+m)
for (i = e; i <= d-m; i += m+m)
merge(a, i, i+m-1, min(i+m+m-1, d));
}
Considerações
8
} Vantagens
} Ordena vetor com N elementos e tempo proporcional a
NlogN, não importa a entrada.
} Deve ser considerado quando alto custo de pior caso não
pode ser tolerável.
} Método de ordenação estável.
} Desvantagens
} Requer espaço extra proporcional a N.
} Não é adaptável (tempo de execução independe dos dados
da entrada).
AEDSII_aula_019_radixsort.pdf
Ordenação: Radixsort
Algoritmos e Estruturas de Dados II
Radixsort
} Algumas vezes, a comparação entre chaves pode ser
uma operação muito cara
} Existem alguns algoritmos de ordenação sem
comparação de chaves
} Bucket Sort
} Counting Sort
} Tally Sort
} etc...
} Radix Sort é uma classe de algoritmos que usa a
representação binária das chaves para a ordenação
Introdução
3
} Até agora vimos métodos de ordenação que
comparam chaves
} Esta é uma abordagem geral que funciona para qualquer tipo
de chave
} Uma abordagem alternativa para ordenação é
processar as chaves por partes
} Por exemplo, começamos pelas primeiras letras do nome
quando procuramos um nome num catálogo
} Não precisamos comparar chaves
Ideia
4
} Quebrar uma chave em vários pedaços
} Dígitos de um número em uma dada base (radix)
} 312 tem os dígitos 3, 1 e 2 na base 10
} 312 tem os dígitos 100111000 na base 2
} “exemplo” tem 6 caracteres (base 256)
} Ordenar de acordo com o primeiro pedaço
} Números cujo dígito mais à esquerda começa com 0 vêm
antes de números cujo dígito mais à esquerda é 1
} Podemos ordenar repetindo esse processo para
todos os pedaços
5
Algoritmos e Estrutura de
Dados II
Radixsort
} Idéia Geral:
} chaves cujo bit mais a esquerda é 0, vem antes que chaves
cujo bit é 1
} Repetindo-se isso para todos os bits de forma adequada é
possível ordenar
} Como extrair os bits
} Formas eficientes em c: and (&) e shift(>>)
} bit = x & 00000001; x >> 1;
} Formas simples: divisão e resto
} Considerando bits indexados de 0 a n da dir para esq, para
extrair o bit i de um número X, temos (X / 2i) % 2
Algoritmos e Estrutura de
Dados II
Radix Exchange Sort
} Algoritmo analisa os bits da esquerda para a direita
} Funcionamento similar ao do Quicksort, mas a
partição é feita comparando-se bits ao invés de
chaves
} Chamadas recursivas ordenando os subvetores pelo
bit i-1
} Complexidade:
} O(n * b) comparações de bits
Algoritmos e Estrutura de
Dados II
Radix Exchange Sort
quicksortB(int a[], int l, int r, int w) {
int i = l, j = r;
if (r <= l || w > 0) return;
while (j != i) {
while (digit(a[i], w) == 0 && (i < j)) i++;
while (digit(a[j], w) == 1 && (j > i)) j--;
exch(a[i], a[j]);
}
if (digit(a[r], w) == 0) j++;
quicksortB(a, l, j-1, w+1);
quicksortB(a, j, r, w+1);
}
void sort(Item a[], int l, int r) {
quicksortB(a, l, r, numbits - 1);
}
Fonte: Algorithms in C
Robert Sedgewick
Algoritmos e Estrutura de
Dados II
Exemplo
[ 3 2 5 6 2 0 7]
[ 011 010 101 110 001 000 111]
Algoritmos e Estrutura de
Dados II
Exemplo
[ 3 2 5 6 2 0 7]
[ 011 010 101 110 001 000 111]
[ 011 010 101 110 001 000 111]
[ 011 010 000 001 110 101 111]
[ 001 000 010 011]
[ 000 001]
[010 011]
[101 110 111]
[110 111]
[ 0 1 2 3 5 6 7]
Radixsort – Ordenando um dígito
11
} Contar quantos elementos existem de cada valor
123 142 087 263 233 014 132 Digito Contador
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
Radixsort – Ordenando um dígito
12
} Para isso iremos contar quantos elementos existem
de cada valor
123 142 087 263 233 014 132 Digito Contador
0 0
1 0
2 2
3 3
4 1
5 0
6 0
7 1
8 0
9 0
Radixsort – Ordenando um dígito
13
} Depois calcular a posição deles no vetor ordenado
123 142 087 263 233 014 132 Dig C Posicao
0 0 0
1 0 0
2 2 0
3 3 2
4 1 5
5 0 0
6 0 0
7 1 6
8 0 0
9 0 0
Radixsort – Ordenando um dígito
14
} E finalmente colocar os elementos em suas posições
123 142 087 263 233 014 132
123
Dig C Posicao
0 0 0
1 0 0
2 2 0
3 3 3
4 1 5
5 0 0
6 0 0
7 1 6
8 0 0
9 0 0
Radixsort – Ordenando um dígito
15
} Para isso iremos contar quantos elementos existem
de cada valor
123 142 087 263 233 014 132
142 123
Dig C Posicao
0 0 0
1 0 0
2 2 1
3 3 3
4 1 5
5 0 0
6 0 0
7 1 6
8 0 0
9 0 0
Radixsort – Ordenando um dígito
16
} Para isso iremos contar quantos elementos existem
de cada valor
123 142 087 263 233 014 132
142 123 087
Dig C Posicao
0 0 0
1 0 0
2 2 1
3 3 3
4 1 5
5 0 0
6 0 0
7 1 7
8 0 0
9 0 0
Radixsort – Ordenando um dígito
17
} Para isso iremos contar quantos elementos existem
de cada valor
123 142 087 263 233 014 132
142 123 263 087
Dig C Posicao
0 0 0
1 0 0
2 2 1
3 3 4
4 1 5
5 0 0
6 0 0
7 1 7
8 0 0
9 0 0
Radixsort – Ordenando um dígito
18
} Para isso iremos contar quantos elementos existem
de cada valor
123 142 087 263 233 014 132
142 123 263 233 087
Dig C Posicao
0 0 0
1 0 0
2 2 1
3 3 5
4 1 5
5 0 0
6 0 0
7 1 7
8 0 0
9 0 0
Radixsort – Ordenando um dígito
19
} Para isso iremos contar quantos elementos existem
de cada valor
123 142 087 263 233 014 132
142 123 263 233 014 087
Dig C Posicao
0 0 0
1 0 0
2 2 1
3 3 5
4 1 6
5 0 0
6 0 0
7 1 7
8 0 0
9 0 0
Radixsort – Ordenando um dígito
20
} Para isso iremos contar quantos elementos existem
de cada valor
123 142 087 263 233 014 132
142 132 123 263 233 014 087
Dig C Posicao
0 0 0
1 0 0
2 2 1
3 3 5
4 1 6
5 0 0
6 0 0
7 1 7
8 0 0
9 0 0
Radixsort – Ordenando o vetor
21
} Repetimos o mesmo processo para o próximo dígito
} Funciona por que o método do contador que usamos
anteriormente é estável!
123 142 087 263 233 014 132
142 132 123 263 233 014 087
014 123 132 233 142 263 087
Radixsort – Ordenando o vetor
22
} Repetimos o mesmo processo para o próximo dígito
} Funciona por que o método do contador que usamos
anteriormente é estável!
123 142 087 263 233 014 132
142 132 123 263 233 014 087
014 123 132 233 142 263 087
014 087 123 132 142 233 263
Radixsort
23
void radix(int *v, int n, int base, int num_digitos) {
int i, j, w, count[base+1], d, idx;
int *aux = (int *) malloc(n * sizeof(int));
for(w = 0; w < num_digitos; w++) {
for(j = 0; j < base; j++) count[j] = 0; // zera contador
for(i = 0; i < n; i++) { // conta dígitos
d = digito(v[i], w, base);
count[d+1]++;
} // seta índices para os dígitos
for(j = 1; j < base; j++) count[j] += count[j-1];
for(i = 0; i < n; i++) { // adiciona nas posições
d = digito(v[i], w, base);
idx = count[d];
count[d] += 1;
aux[idx] = v[i]; }
for(i = 0; i < n; i++) v[i] = aux[i]; // retorna p/ v
}
}
Radixsort – Análise
24
} Nenhuma comparação
} Inspeções de dígitos:
} 2*n*num_digitos
} Se num_digitos for pequeno ou constante, então
radixsort tem custo linear O(n)
} Trocas:
} n*num_digitos
} Número de trocas também é O(n)
Vantagens e desvantagens
25
} Vantagens:
} Estável
} Não compara as chaves
} Desvantagens:
} Nem sempre é fácil otimizar a inspeção de dígitos
} Depende do hardware
} Só é bom se o número de dígitos for pequeno
Exercícios
26
1. Por que não usar o algoritmo de ordenação por
seleção para identificar o k-ésimo menor elemento
do vetor?
2. Mesmo com o uso da estratégia da mediana, mostre
um vetor de entrada que cai no pior caso do
quicksort.
3. Um vetor com elementos em ordem reversa é um
heap?
4. Mostre que o heapsort não é estável.
5. Como seria a implementação do radixsort
utilizando o TAD fila?
Radixsort – Análise
27
} Nenhuma comparação
} Inspeções de dígitos:
} 2*n*num_digitos
} Se num_digitos for pequeno ou constante, então
radixsort tem custo linear O(n)
} Trocas:
} n*num_digitos
} Número de trocas também é O(n)
} Quicksort é comparável ao radixsort porque o
número de dígitos é da ordem de lg(n) na base 2 e
log10(n) na base 10
AEDSII_aula_019a_comparacao_ordenacao.pdf
Comparação entre os métodos
de ordenação
Algoritmos e Estruturas de Dados II
Número de comparações
2
Método Complexidade
Inserção O(n2)
Seleção O(n2)
Bolha O(n2)
Shellsort O(n lg(n)2)
Quicksort O(n lg(n))
Heapsort O(n lg(n))
Radixsort O(kn)
Tempo de execução
3
} O método que levou menos tempo real para
executar recebeu o valor 1 e os outros receberam
valores relativos
} Elementos em ordem aleatória:
Tempo de execução
4
} Elementos em ordem crescente
Tempo de execução
5
} Elementos em ordem decrescente
Observações
6
} Observações sobre os métodos:
} 1. Shellsort, quicksort e heapsort têm a mesma ordem de
grandeza para arranjos de até 30 mil elementos
} 2. O quicksort é o mais rápido para todos os tamanhos aleatórios
experimentados
} 3. A relação heapsort/quicksort se mantém constante para todos
os tamanhos de entrada
} 4. A relação shellsort/quicksort aumenta com o tamanho da
entrada
} 5. Para arquivos pequenos (500 elementos), o shellsort é mais
rápido que o heapsort (e vice versa)
} 6. Inserção é o método mais rápido para qualquer tamanho se os
elementos estão ordenados (e vice versa)
} 7. Entre os algoritmos de custo quadrático, o inserção é melhor
para entradas aleatórias
Influência da ordem inicial dos elementos
7
} 1. O shellsort é bastante sensível à ordenação ascendente
ou descendente da entrada
} 2. Em arquivos do mesmo tamanho, o shellsort executa mais
rápido para arquivos ordenados
} 3. Em arquivos do mesmo tamanho, o quicksort executa
mais rápido para arquivos ordenados
} 4. O heapsort não depende da ordenação da entrada
Inserção
8
} É o mais interessante para arquivos com menos do
que 20 elementos
} O método é estável
} Possui comportamento melhor do que o método da
bolha que também é estável
} Sua implementação é tão simples quanto as
implementações do bolha e seleção
} Para arquivos já ordenados, o método é O(n)
} O custo é linear para
adicionar alguns elementos a
um arquivo já ordenado
Seleção
9
} É vantajoso quanto ao número de movimentos de
registros, que é O(n)
} Deve ser usado para arquivos com elementos muito
grandes, desde que o número de elementos a
ordenar seja pequeno
Shellsort
10
} Bom para ordenar um número moderado de
elementos
} Quando encontra um arquivo parcialmente ordenado
trabalha menos
Quicksort
11
} É o algoritmo mais eficiente que existe para uma grande
variedade de situações
} O algoritmo é recursivo, o que demanda uma pequena
quantidade de memória adicional
} Pior caso realiza O(n2) operações
} O principal cuidado a ser tomado é com relação à
escolha do pivô
} A escolha do elemento do meio do arranjo melhora o
desempenho quando o arquivo está total ou parcialmente
ordenado
} O pior caso tem uma probabilidade muito pequena de ocorrer
quando os elementos forem aleatórios
} Geralmente se usa a mediana de uma amostra de três elementos
para evitar o pior caso
} Usar inserção em partições pequenas melhora
desempenho significativamente
Heapsort
12
} É um método de ordenação elegante e eficiente
} Não necessita de nenhuma memória adicional
} Executa sempre em tempo proporcional a
O(n lg(n))
} Aplicações que não podem tolerar eventuais
variações no tempo esperado de execução devem
usar o heapsort
AEDSII_aula_020_pesquisa_sequencial_e_binaria_arvore_bin_pesq.pdf
Pesquisa em Memória Primária
Algoritmos e Estruturas de Dados II
Pesquisa em Memória Primária
2
} Pesquisa:
} Recuperação de informação em um grande volume de
dados.
} Informação é dividida em registros e cada registro contém
uma chave.
} Objetivo:
} Encontrar itens com chaves iguais à chave dada na pesquisa.
} Aplicações:
} Contas em um banco
} Reservas de uma companhia aérea
Pesquisa em Memória Primária
3
} Escolha do método de busca
} Quantidade de dados envolvidos.
} Frequência com que operações de inserção e retirada são
efetuadas.
} Métodos de pesquisa:
} Pesquisa sequencial
} Pesquisa binária
} Árvore de pesquisa
} Árvores binárias de pesquisa sem balanceamento
} Árvores binárias de pesquisa com balanceamento
} Pesquisa digital
} Hashing
Tabelas de Símbolos
4
} Estrutura de dados contendo itens com chaves que
suportam duas operações
} Inserção de um novo item
} Retorno de um item que contém uma determinada chave.
} Tabelas são também conhecidas como dicionários
} Chaves – palavras
} Item – entradas associadas as palavras (significado,
pronúncia)
Tipo Abstrato de Dados
5
n Considerar os algoritmos de pesquisa como tipos
abstratos de dados (TADs), com um conjunto de
operações associado a uma estrutura de dados,
n Há independência de implementação para as operações.
} Operações:
} Inicializar a estrutura de dados
} Pesquisar um ou mais registros com uma dada chave
} Inserir um novo registro
} Remover um registro específico
} Ordenar os registros
Pesquisa Sequencial
6
} Método de pesquisa mais simples
} A partir do primeiro registro, pesquisa sequencialmente até
encontrar a chave procurada
} Registros ficam armazenados em um vetor (arranjo).
} Inserção de um novo item
} Adiciona no final do vetor.
} Remoção de um item com chave específica
} Localiza o elemento, remove-o e coloca o último item do
vetor em seu lugar.
Pesquisa Sequencial
7
# define MAX 10
typedef int TipoChave;
typedef struct {
TipoChave Chave;
/* outros componentes */
} Registro;
typedef int Indice;
typedef struct {
Registro Item[MAX + 1];
Indice n;
} Tabela;
Pesquisa Sequencial
8
void Inicializa(Tabela *T) {
T->n = 0;
}
/* retorna 0 se não encontrar um registro com a chave x */
Indice Pesquisa(TipoChave x, Tabela *T){
int i;
T->Item[0].Chave = x; /* sentinela */
i = T->n + 1;
do {
i--;
} while (T->Item[i].Chave != x);
return i;
}
Pesquisa Sequencial
9
void Insere(Registro Reg, Tabela *T) {
if (T->n == MAX)
printf("Erro : tabela cheia\n");
else {
T->n++;
T->Item[T->n] = Reg;
}
}
void Remove(TipoChave x, Tabela *T) {
Int idx;
idx = Pesquisa(x, T);
/* se encontrou o item, troca pelo último, reduz o n */
if (idx) T->Item[idx] = T->Item[T->n--];
}
Pesquisa Sequencial
10
} Análise:
} Pesquisa com sucesso
} melhor caso: C(n) = 1
} pior caso: C(n) = n
} caso médio: C(n) = (n+1) / 2
} Pesquisa sem sucesso
} C(n) = n + 1
Pesquisa Binária
11
} Redução do tempo de busca aplicando o paradigma
dividir para conquistar.
1. Divide o vetor em duas partes
2. Verifica em qual das partes o item com a chave se localiza
3. Concentra-se apenas naquela parte
} Restrição: chaves precisam estar ordenadas
} Manter chaves ordenadas na inserção pode levar a
comportamento quadrático.
} Se chaves estiverem disponíveis no início, um método de
ordenação rápido pode ser usado.
} Trocas de posições podem reduzir a eficiência.
Pesquisa Binária
12
} Exemplo: pesquisa pela chave L
A A A C E E E G H I L M N P R
A A A C E E E G H I L M N P R
H I L M N P R
H I L
L
Pesquisa Binária
13
} Exemplo: pesquisa pela chave J
A A A C E E E G H I L M N P R
A A A C E E E G H I L M N P R
H I L M N P R
H I L
L
Pesquisa Binária
14
Indice Binaria(TipoChave x, Tabela *T) {
Indice i, Esq, Dir;
if (T->n == 0) return 0; /* vetor vazio */
Esq = 1;
Dir = T->n;
do {
i = (Esq + Dir) / 2;
if (x > T->Item[i].Chave)
Esq = i + 1; /* procura na partição direita */
else
Dir = i - 1; /* procura na partição esquerda */
}
while ((x != T->Item[i].Chave) && (Esq <= Dir));
if (x == T->Item[i].Chave)
return i;
else
return 0;
Pesquisa Binária
15
} Análise
} A cada iteração do algoritmo, o tamanho da tabela é dividido
ao meio.
} Logo, o número de vezes que o tamanho da tabela é dividido
ao meio é cerca de log n.
} Ressalva
} Alto custo para manter a tabela ordenada: a cada inserção
na posição p da tabela implica no deslocamento dos
registros a partir da posição p para as posições seguintes.
} Portanto, a pesquisa binária não deve ser usada em
aplicações muito dinâmicas.
Árvore Binária de Pesquisa
} Árvores de pesquisa mantêm uma ordem entre seus
elementos
} Raiz é maior que os elementos na árvore à esquerda
} Raiz é menor que os elementos na árvore à direita
Árvore Binária de Pesquisa
struct arvore {
struct arvore *esq;
struct arvore *dir;
Registro reg;
};
struct arvore *cria_arvore(Registro reg) {
struct arvore *novo;
novo = malloc(sizeof(struct arvore));
novo->esq = NULL;
novo->dir = NULL;
novo->reg = reg;
}
0
Árvore Binária de Pesquisa: Busca
void Pesquisa(Registro *x, struct arvore *t) {
if (t == NULL) {
printf("Registro não esta presente na árvore\n");
}
else if (x->Chave < t->reg.Chave)
Pesquisa(x, t->Esq); /* busca no filho
esquerdo */
else if (x->Chave > t->reg.Chave)
Pesquisa(x, t->Dir); /* busca no filho direito */
else
*x = t->reg;
}
Árvore Binária de Pesquisa: Busca
8 5
6
4 B
2 A C
1 3 9
7
Árvore Binária de Pesquisa: Inserção
} O elemento vai ser inserido como uma folha da
árvore de busca
} Vamos procurar o lugar de inserção navegando da
raiz até a folha onde ele será inserido
Árvore Binária de Pesquisa: Inserção
8 5
6
4 B
2 A C
1 3 9
7
4.5
Árvore Binária de Pesquisa: Inserção
8 5
6
4 B
2 A C
1 3 9
7
4.5
Árvore Binária de Pesquisa: Inserção
8 5
6
4 B
2 A C
1 3 9
7 4.5
Árvore Binária de Pesquisa: Inserção
8 5
6
4 B
2 A C
1 3 9
7
4.5
Árvore Binária de Pesquisa: Inserção
void insere_elemento(struct arvore *t, Registro reg) {
if(reg.Chave < t->reg.Chave) { /* chave menor */
if (t->esq) { insere_elemento(t->esq, reg); }
else { /* achou local de inserção */
struct arvore *novo = cria_arvore(reg);
t->esq = novo;
}
} else { /* chave maior ou igual ao nodo atual */
if (t->dir) { insere_elemento(t->dir, reg); }
else {
struct arvore *novo = cria_arvore(reg);
t->dir = novo;
}
}
}
Árvore Binária de Pesquisa: Remoção
} Remover folhas
} Remover nós com um filho
} Remover nós com
dois filhos
8 5
6
4 B
2 A C
1 3 9
7
Árvore Binária de Pesquisa: Remoção
} Nó com 1 filho
8 5
6
4 B
2 A C
1 3 9
7
Árvore Binária de Pesquisa: Remoção
} Nó com 1 filho
8 5
6
B2
A C1 3
9
7
Árvore Binária de Pesquisa: Remoção
} Nó com 2 filhos
8 5
6
4 B
2 A C
1 3 9
7
Árvore Binária de Pesquisa: Remoção
8 5
7
4 B
2 A C
1 3 9
7
} Nó com 2 filhos
Árvore Binária de Pesquisa: Remoção
8 5
7
4 B
2 A C
1 3 9
7
} Nó com 2 filhos
Árvore Binária de Pesquisa: Remoção
struct arvore *remove(struct arvore *t, TipoChave Chave) {
struct arvore *aux;
if(t == NULL) { printf(“elemento ausente\n”); }
else if(Chave < t->reg.Chave){ t->esq=remove(t->esq, Chave); }
else if(Chave > t->reg.Chave){ t->dir=remove(t->dir, Chave); }
else if (t->esq == NULL && t->dir == NULL) {
free(t); return NULL; /* zero filhos */
}
else if(t->esq == NULL) {
aux = t->dir; free(t); return aux; /* 1 filho direita */
}
else if(t->dir == NULL) {
aux = t->esq; free(t); return aux; /* 1 filho esquerda */
} else { /* 2 filhos */
struct arvore *suc = acha_menor(t->dir);
t->reg = suc->reg;
t->dir = remove(t->dir, suc->reg.Chave);
return t;
}
return t;
}
Árvore Binária de Pesquisa: Remoção
void acha_menor(arvore *t) {
if(t->esq == NULL) {
return t;
}
return acha_menor(t->esq);
}
Árvore Binária de Pesquisa: Análise
} Número de comparações: busca com sucesso
} melhor caso: C(n) = O(1)
} pior caso: C(n) = O(n)
} caso médio: C(n) = O(log n)
AEDSII_aula_021_arvores_binarias_de_pesquisa_SBB.pdf
Árvores binárias de pesquisa
com balanceamento
Algoritmos e Estruturas de Dados II
Árvores binárias de pesquisa
2
} Pior caso para uma busca é O(n)
3
1
4
5
6
2
Ordem de inserção:
1 3 2 4 5 6
Árvore completamente balanceada
3
} Nós folha (externos) aparecem em no máximo dois
níveis diferentes
} Minimiza o tempo médio de pesquisa
} Assumindo distribuição uniforme das chaves
} Problema: manter árvore completamente balanceada
após cada inserção é muito caro
Árvore completamente balanceada
4
} Para inserir a chave 1 na árvore à esquerda e manter
a árvore completamente balanceada precisamos
movimentar todos os nós
Árvores “quase balanceadas”
5
} Objetivo:
} Funções para pesquisar, inserir e retirar eficientes
} O(lg(n))
} Solução intermediária que mantém a árvore “quase
balanceada”, em vez de tentar manter a árvore
completamente balanceada
Árvores “quase balanceadas”
6
} Várias formas de definir e construir uma árvore
“quase balanceada”
} Exemplos de restrições aplicadas a árvores para fazê-
las “quase balanceadas”
} Restringir a diferença entre as alturas das subárvores de
cada nó
} Minimizar o comprimento do caminho interno da árvore
8 = 0 + 1 + 1 + 2 + 2 + 2
Árvores SBB
7
} Uma árvore SBB é uma árvore binária com
apontadores verticais e horizontais, tal que:
} Todos os caminhos da raiz até cada nó externo possuem o
mesmo número de apontadores verticais
} Não podem existir dois apontadores horizontais sucessivos
Árvores SBB – estrutura
8
#define SBB_VERTICAL 0
#define SBB_HORIZONTAL 1
struct sbb {
struct registro reg;
struct sbb *esq;
struct sbb *dir;
int esqtipo;
int dirtipo;
}
Pesquisa em árvore SBB
9
} Idêntica à pesquisa em uma árvore de busca binária
não balanceada
} Ignoramos a direção dos apontadores
Inserção numa árvore SBB
10
} A chave a ser inserida é sempre inserida após o
apontador vertical mais baixo na árvore
} Dependendo da situação anterior à inserção podem
aparecer dois apontadores horizontais
} Transformação local para manter as propriedades da
árvore SBB
Inserção do 4, 6, 8, 11?
Criação de um nó
11
struct sbb *cria_no(struct registro reg) {
struct sbb *no = malloc(sizeof(struct sbb));
no->reg = reg;
no->esq = NULL;
no->dir = NULL;
no->esqtipo = SBB_VERTICAL;
no->dirtipo = SBB_VERTICAL;
return no;
}
} Métodos para reorganizar casos onde aparecem dois
ponteiros horizontais consecutivos
} Esquerda-esquerda (e direita-direita)
} Esquerda-direita (e direita-esquerda)
Transformações para manter
propriedadas da árvore SBB
12
Transformações para manter
propriedadas da árvore SBB - código
13
void ee(struct sbb **ptr) {
struct sbb *no = *ptr;
struct sbb *esq = no->esq;
no->esq = esq->dir;
esq->dir = no;
esq->esqtipo = SBB_VERTICAL;
no->esqtipo = SBB_VERTICAL;
*ptr = esq;
}
ptr
no esq
x
x
ptr
Transformações para manter
propriedadas da árvore SBB - código
14
void dd(struct sbb **ptr) {
struct sbb *no = *ptr;
struct sbb *dir = no->dir;
no->dir = dir->esq;
dir->esq = no;
dir->dirtipo = SBB_VERTICAL;
no->dirtipo = SBB_VERTICAL;
*ptr = dir;
} ptr
1 2 3
x
ptr
dir no
x
Transformações para manter
propriedadas da árvore SBB - código
15
void ed(struct sbb **ptr) {
struct sbb *no = *ptr;
struct sbb *esq = no->esq;
struct sbb *dir = esq->dir;
esq->dir = dir->esq;
no->esq = dir->dir;
dir->esq = esq;
dir->dir = no;
esq->dirtipo = SBB_VERTICAL;
no->esqtipo = SBB_VERTICAL;
*ptr = dir;
}
ptr
no esq dir
x y
x y
ptr
Transformações para manter
propriedadas
da árvore SBB - código
16
void de(struct sbb **ptr) {
struct sbb *no = *ptr;
struct sbb *dir = no->dir;
struct sbb *esq = dir->esq;
no->dir = esq->esq;
dir->esq = esq->dir;
esq->esq = no;
esq->dir = dir;
dir->esqtipo = SBB_VERTICAL;
no->dirtipo = SBB_VERTICAL;
*ptr = esq;
}
esq
1 2 3
x
ptr dir no
y
ptr
x y
Exemplo de inserção em árvore SBB
17
} Inserir chaves 7, 10, 5, 2, 4, 9, 3, 6
Exemplo de inserção em árvore SBB
18
} Inserir chaves 7, 10, 5, 2, 4, 9, 3, 6
Inserção em árvores SBB
19
void iinsere(struct registro reg, struct sbb **ptr,
int *incli, int *fim) {
/* adiciona, pois encontrou uma folha */
if(*ptr == NULL)
iinsere_aqui(reg, ptr, incli, fim);
/* busca na sub-árvore esquerda */
} else if (reg.chave < *ptr->reg.chave) {
iinsere(reg, &(*ptr->esq), &(*ptr->esqtipo), fim);
if (*fim) return;
if (*ptr->esqtipo == SBB_VERTICAL) {
*fim = TRUE;
} else if (*ptr->esq->esqtipo == SBB_HORIZONTAL) {
ee(ptr); *incli = SBB_HORIZONTAL;
} else if (*ptr->esq->dirtipo == SBB_HORIZONTAL) {
ed(ptr); *incli = SBB_HORIZONTAL;
}
}
/* continua */
Inserção em árvores SBB
20
/* busca na sub-árvore direita */
} else if (reg.chave > (*ptr)->reg.chave) {
iinsere (reg, &(*ptr->dir), &(*ptr->dirtipo), fim);
if (*fim) return;
if (*ptr->dirtipo == SBB_VERTICAL) {
*fim = TRUE;
} else if (*ptr->dir->dirtipo == SBB_HORIZONTAL) {
dd(ptr); *incli = SBB_HORIZONTAL;
} else if (*ptr->dir->esqtipo == SBB_HORIZONTAL) {
de(ptr); *incli = SBB_HORIZONTAL;
}
/* chave já existe */
} else {
printf(“erro: chave já está na árvore.\n”);
*fim = TRUE;
}
}
Inserção em árvores SBB
21
void iinsere_aqui(struct registro reg, struct sbb **ptr,
int *incli, int *fim) {
struct sbb *no = malloc(sizeof(struct sbb));
no->reg = reg;
no->esq = NULL;
no->dir = NULL;
no->esqtipo = SBB_VERTICAL;
no->dirtipo = SBB_VERTICAL;
*ptr = no;
*incli = SBB_HORIZONTAL;
*fim = FALSE;
}
Inserção em árvores SBB
22
void insere(struct registro reg, struct sbb **raiz)
{
int fim = FALSE;
int inclinacao = SBB_VERTICAL;
iinsere(reg, raiz, &inclinacao, &fim);
}
void inicializa(struct sbb **raiz)
{
*raiz = NULL;
}
Exemplo de inserção em árvore SBB
23
} Inserir a chave 5.5 na árvore a seguir
SBBs – análise
24
} Dois tipos de altura
} Altura vertical h: conta o número de apontadores verticais
da raiz até as folhas
} Altura k: o número de ponteiros atravessados (comparações
realizadas) da raiz até uma folha
} A altura k é maior que a altura h sempre que
existirem apontadores horizontais na árvore
} Para qualquer árvore SBB temos hkh 2≤≤
SBBs – análise
25
} Bayer (1972) mostrou que
} Custo para manter a propriedade SBB depende da
altura da árvore O(lg(n))
} Número de comparações em uma pesquisa com
sucesso numa árvore SBB
} Melhor caso: C(n) = O(1)
} Pior caso: C(n) = O(lg(n))
} Caso médio: C(n) = O(lg(n))
2221 −+≤≤+ )lg()lg( nkn
Exercícios
26
} Desenhe a árvore SBB resultante da inserção das
chaves Q U E S T A O F C I L em uma árvore vazia.
} Dê a lista de inserções que gera a árvore SBB abaixo:
6
8 5
4
2
Retirada numa árvore SBB
27
} Usaremos três procedimentos auxiliares
} EsqCurto: chamado quando o nó (referenciado por um
apontador vertical) é retirado à esquerda e diminui a altura
da árvore
} DirCurto: chamado quando um nó (referenciado por um
apontador vertical) é retirado à direita e diminui a altura da
árvore
} Antecessor: chamado quando um nó possui dois filhos
Retirada em árvore SBB – exemplos
28
Retirando 7, 5 e 9:
Retirada em árvore SBB – exemplos
29
Retirada em árvore SBB – exemplos
30
Retirada em árvore SBB – exemplos
31
Retirada em árvore SBB – exemplos
32
Retirada de árvore SBB – código
33
void iretira(struct registro reg, struct sbb **ptr, int *fim)
{
/* chegou a um nó vazio e não encontrou chave */
if (*ptr == NULL) {
*fim = TRUE;
return;
}
/* busca na sub-árvore esquerda */
if (reg.chave < *ptr->reg.chave) {
iretira(reg, &(*ptr->esq), fim);
if(!(*fim))
EsqCurto(ptr, fim);
}
/* busca na sub-árvore direita */
else if (reg.chave > *ptr->reg.chave) {
iretira(reg, &(*ptr->dir), fim);
if(!(*fim))
DirCurto(ptr, fim);
}
/* continua */
Retirada de árvore SBB – código
34
else { /* encontrou o registro */
*fim = FALSE;
struct sbb *no = *ptr;
if (no->dir == NULL) { /* sem filho direito */
*ptr = no->esq;
free(no);
if (*ptr != NULL) { *fim = TRUE; }
}
else if (no->esq == NULL) { /* sem filho esquerdo */
*ptr = no->dir;
free(no);
if (*ptr != NULL) { *fim = TRUE; }
}
} else { /* com dois filhos */
antecessor(ptr, &(*ptr->esq), fim);
if (!(*fim))
EsqCurto(ptr, fim);
}
}
}
Retirada de árvore SBB – código
35
void antecessor(struct sbb **q, struct sbb **ptr, int *fim) {
/* busca pelo maior elemento */
if (*ptr->dir != NULL) {
antecessor (q, &(*ptr->dir), fim);
if (!(*fim)) {
DirCurto(ptr, fim);
return;
}
}
/* encontrou o maior elemento */
*q->reg = *ptr->reg;
q = ptr;
*ptr = *ptr->esq;
free(*q);
if (*ptr != NULL)
*fim = TRUE;
Retirada de árvore SBB – código
36
void EsqCurto(struct sbb **ptr, int *fim) {
if (*ptr->esqtipo == SBB_HORIZONTAL) {
*ptr->esqtipo = SBB_VERTICAL; *fim = TRUE;
} else if (*ptr->dirtipo == SBB_HORIZONTAL) {
struct sbb *dir = *ptr->dir;
*ptr->dir = dir->esq;
dir->esq = *ptr;
*ptr = dir;
if (*ptr->esq->dir->esqtipo == SBB_HORIZONTAL) {
de(&(*ptr->esq)); *ptr->esqtipo = SBB_HORIZONTAL;
} else if (*ptr->esq->dir->dirtipo == SBB_HORIZONTAL)
{
dd(&(*ptr->esq)); *ptr->esqtipo = SBB_HORIZONTAL;
}
*fim = TRUE;
} else {
*ptr->dirtipo = SBB_HORIZONTAL;
if(*ptr->dir->esqtipo == SBB_HORIZONTAL) {
de(ptr); *fim = TRUE;
} else if(/* checa outro lado */) { ... }
}}}
Retirada de árvore SBB – código
37
void DirCurto(struct sbb **ptr, int *fim) {
if(*ptr->dirtipo == SBB_HORIZONTAL) {
*ptr->dirtipo = SBB_VERTICAL; *fim = TRUE;
} if (*ptr->esqtipo == SBB_HORIZONTAL) {
struct sbb *esq = *ptr->esq;
*ptr->esq = esq->dir;
esq->dir = *ptr;
*ptr = esq;
if(*ptr->dir->esq->dirtipo == SBB_HORIZONTAL) {
ed(&(*ptr->dir)); *ptr->dirtipo = SBB_HORIZONTAL;
} else if(*ptr->dir->esq->esqtipo == SBB_HORIZONTAL) {
ee(&(*ptr->dir)); *ptr->dirtipo = SBB_HORIZONTAL;
}
*fim = TRUE;
}
*ptr->esqtipo = SBB_HORIZONTAL;
if(*ptr->esq->dirtipo == SBB_HORIZONTAL) {
ed(ptr); *fim = TRUE; }
if(*ptr->esq->esqtipo == SBB_HORIZONTAL) {
ee(ptr); *fim = TRUE; }
}}}
AEDSII_aula_022_hashing.pdf
Pesquisa em memória
primária: hashing
Algoritmos e Estruturas de Dados II
Hashing
2
} Algoritmos vistos efetuam comparações para localizar
uma chave.
} Os registros armazenados em uma tabela são
diretamente endereçados a partir de uma
transformação aritmética sobre a chave de pesquisa.
} Busca por meio de operações aritméticas que
transformam a chave em endereços em uma tabela.
Hashing
3
} Um método de pesquisa com o uso da transformação de chave é
constituído de duas etapas principais:
} Computar o valor da função de transformação, a qual transforma a
chave de pesquisa em um endereço da tabela.
} Considerando que duas ou mais chaves podem ser transformadas em
um mesmo endereço de tabela, é necessário existir um método para
lidar com colisões.
20
10
23
74
x%10
função hashing
0 20
1 10
2
3 23
4 74
tabela
Hashing: colisões
4
} Qualquer que seja a função de transformação,
algumas colisões irão ocorrer fatalmente, e tais
colisões têm de ser resolvidas de alguma forma.
} Mesmo que se obtenha uma função de transformação
que distribua os registros de forma uniforme entre as
entradas da tabela, existe uma alta probabilidade de
haver colisões.
Hashing: colisões
5
} O paradoxo do aniversário (Feller,1968, p. 33), diz que
em um grupo de 23 ou mais pessoas, juntas ao acaso,
existe uma chance maior do que 50% de que 2
pessoas comemorem aniversário no mesmo dia.
} Para hashing:
} Tabela com 365 posições
} Adição de 23 chaves
} Chance > 50% de haver colisão
Hashing: colisões
6
} A probabilidade p de se inserir N itens consecutivos
sem colisão em uma tabela de tamanho M é:
Hashing: colisões
7
} Seja uma tabela com 50.063.860 de posições (M):
Chaves (N) Chance de colisão Fator de carga (N/M)
1000 0.995% 0.002%
2000 3.918% 0.004%
4000 14.772% 0.008%
6000 30.206% 0.012%
8000 47.234% 0.016%
10000 63.171% 0.020%
12000 76.269% 0.024%
14000 85.883% 0.028%
16000 92.248% 0.032%
18000 96.070% 0.036%
20000 98.160% 0.040%
22000 99.205% 0.044%
Função de Transformação
8
} Uma função de transformação deve mapear chaves
em inteiros dentro do intervalo [0...M − 1], onde M é
o tamanho da tabela.
} A função de transformação ideal é aquela que:
} Seja simples de ser computada.
} Para cada chave de entrada, qualquer uma das saídas
possíveis é igualmente provável de ocorrer.
} Exemplo:
} Usa o resto da divisão por M (onde k é a chave)
h(k) = k % M
Chaves não Numéricas
9
} As chaves não numéricas devem ser transformadas
em números:
n n é o número de caracteres da chave.
n Chave[i] corresponde à representação ASCII do i-
ésimo caractere da chave.
n p[i] é um inteiro de um conjunto de pesos gerados
para 1 ≤ i ≤ n.
∑
=
−×=
n
i
iniChaveH
1
128][
H
Chaves não numéricas
10
Indice h(TipoChave Chave, TipoPesos p) {
unsigned int Soma = 0;
int i;
int comp = strlen(Chave);
for (i = 0; i < comp; i++)
Soma += (unsigned int) Chave[i] * p[i];
return (Soma % M);
}
Resolução de Colisões
11
} Encadeamento
} Endereçamento aberto
Resolução de Colisões - Encadeamento
12
} Cria uma lista encadeada para cada endereço da
tabela.
} Todas as chaves com mesmo endereço na tabela são
encadeadas em uma lista linear.
0 U
tabela
1 A
P 2
3
4
5
E
Q
I
S T
Resolução de Colisões – Encadeamento
13
} Exemplo: Considerando a i-ésima letra do alfabeto
representada por i e a função de transformação
h(Chave) = Chave mod M (M=10). Insira EXEMPLO
na tabela hashing.
E
=
5
X
=
25
M
=
13
P
=
16
L
=
12
O
=
15
Estrutura de Dicionário para
Encadeamento
14
#define M 10
#define n 5
typedef char TipoChave[n];
typedef unsigned int TipoPesos[n];
typedef struct {
/* outros componentes */
TipoChave Chave;
} TipoItem;
typedef unsigned int Indice;
typedef struct _celula* Apontador;
typedef TipoLista TipoDicionario[M];
typedef struct _celula {
TipoItem Item;
Apontador Prox;
} Celula;
typedef struct {
Celula *Primeiro, *Ultimo;
} TipoLista;
TipoDicionario
M
Item Prox
Celula
TipoLista
Estrutura de Dicionário para
Encadeamento
15
void Inicializa(TipoDicionario T) {
int i;
for (i = 0; i < M; i++) /* inicializa as M listas */
FLVazia(&T[i]);
}
Estrutura de Dicionário para
Encadeamento
16
Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T){
/* Apontador de retorno aponta para o item anterior da lista */
Indice i; Apontador Ap;
i = h(Ch, p);
if (Vazia(T[i])) return NULL; /* Pesquisa sem sucesso */
else {
Ap = T[i].Primeiro;
while ((Ap->Prox->Prox != NULL) &&
(strncmp(Ch, Ap->Prox->Item.Chave, sizeof(TipoChave))))
{ Ap = Ap->Prox;}
if (!strncmp(Ch, Ap->Prox->Item.Chave, sizeof(TipoChave)))
return Ap;
else return NULL; /* Pesquisa sem sucesso */
}
}
Estrutura de Dicionário para
Encadeamento
17
void InsereHashing(TipoItem x, TipoPesos p, TipoDicionario T) {
Indice i;
if (Pesquisa(x.Chave, p, T) == NULL)
/* insere do TAD Lista */
Insere(x, &T[h(x.Chave, p)]);
else
printf(“Registro ja esta presente\n");
}
void RetiraHashing(TipoItem x, TipoPesos p, TipoDicionario T) {
Apontador Ap = Pesquisa(x.Chave, p, T);
if (Ap == NULL)
printf(" Registro nao esta presente\n");
else
Retira(Ap, &T[h(x.Chave, p)], &x); /*Retira do TAD Lista*/
}
Encadeamento: Análise
18
} Tamanho esperado de cada lista: N/M
} Assumindo que qualquer item do conjunto tem igual
probabilidade endereçado para qualquer entrada de T.
} N: número de registros, M: tamanho da tabela
} Operações Pesquisa, InsereHashing e RetiraHashing:
O(1 + N/M)
} 1: tempo para encontrar a entrada na tabela
} N/M: tempo para percorrer a lista
} M ~ N, tempo se torna constante.
Resolução de Colisões: Endereçamento
Aberto
19
} Quando o número de registros a serem armazenados
na tabela puder ser previamente estimado, não há
necessidade de se utilizar apontadores.
} Para tabela com tamanho M (M > N), pode-se utilizar
os espaços vazios da própria tabela para resolver as
colisões.
} Endereçamento aberto: chaves são armazenadas
na própria tabela.
Resolução de Colisões: Endereçamento
Aberto
20
} Quando encontra uma colisão, procura localizações
alternativas (hj).
} Hashing linear
} Hashing quadrático
11 para , mod ))(( −≤≤+= MjMjxhhj
Mjxhhj mod ))((
2+=
Endereçamento Aberto: Exemplo
21
} Se a i-ésima letra do alfabeto é representada pelo
número i e a função de transformação abaixo é
utilizada
h(Chave) = Chave mod M
No exemplo, considera-se M = 7
} O resultado da inserção das chaves L U N E S na
tabela, usando hashing linear (j = 1) para resolver
colisões é mostrado a seguir.
Endereçamento Aberto: Exemplo
22
h(L) = h(12) = 5
h(U) = h(21) = 0
h(N) = h(14) = 0
h(E) = h(5) = 5
h(S) = h(19) = 5
Endereçamento Aberto: Implementação
23
#define Vazio "!!!!!!!!!!"
#define Retirado "**********"
#define M 7
#define n 11 /* Tamanho da chave */
typedef unsigned int Apontador;
typedef char TipoChave[n];
typedef unsigned TipoPesos[n];
typedef struct {
/* outros componentes */
TipoChave Chave;
} TipoItem;
typedef unsigned int Indice;
typedef TipoItem TipoDicionario[M];
Endereçamento Aberto: Implementação
24
void Inicializa(TipoDicionario T) {
int i;
/* inicializa todas as posições como vazias */
for (i = 0; i < M; i++)
strcpy(T[i].Chave, Vazio);
}
Endereçamento Aberto: Implementação
25
Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T) {
unsigned int i = 0;
unsigned int Inicial;
Inicial = h(Ch, p); /* transforma a chave */
while ((strcmp(T[(Inicial + i) % M].Chave, Vazio) != 0) &&
(strcmp(T[(Inicial + i) % M].Chave, Ch) != 0) &&
(i < M))
i++;
if (strcmp(T[(Inicial + i) % M].Chave, Ch) == 0)
return ((Inicial + i) % M);
else
return M; /* Pesquisa sem sucesso */
}
Endereçamento Aberto: Implementação
26
void Retira(TipoChave Ch, TipoPesos p, TipoDicionario T)
{
Indice i;
i = Pesquisa(Ch, p, T);
if (i < M) /* registro encontrado */
strcpy(T[i].Chave, Retirado);
else
printf("Registro nao esta presente\n");
}
Endereçamento Aberto: Implementação
27
void Insere(TipoItem x, TipoPesos p, TipoDicionario T) {
unsigned int i = 0;
unsigned int Inicial;
if (Pesquisa(x.Chave, p, T) < M) {
printf("Elemento ja esta presente\n");
return;
}
Inicial = h(x.Chave, p); /* transforma a chave */
while ((strcmp(T[(Inicial + i) % M].Chave, Vazio) != 0) &&
(strcmp(T[(Inicial + i) % M].Chave, Retirado) != 0) &&
(i < M))
i++;
if (i < M) {
strcpy (T[(Inicial + i) % M].Chave, x.Chave);
/* Copiar os demais campos de x, se existirem */
}
else printf(“Tabela cheia\n");
}
Endereçamento Aberto: Análise
28
} Seja α = N / M o fator de carga da tabela. Conforme
demonstrado por Knuth (1973), o custo de uma pesquisa com
sucesso é
} O hashing linear sofre de um mal chamado agrupamento.
} Ocorre na medida em que a tabela começa a ficar cheia, pois a
inserção de uma nova chave tende a ocupar uma posição na tabela
que esteja contígua a outras posições já ocupadas, o que deteriora
o tempo necessário para novas pesquisas.
⎟
⎠
⎞
⎜
⎝
⎛
−
+=
α1
11
2
1)(nC
Endereçamento Aberto: Análise
29
α = N / M C(n)
0.1000 1.0556
0.2000 1.1250
0.3000 1.2143
0.4000 1.3333
0.5000 1.5000
0.6000 1.7500
0.7000 2.1667
0.8000 3.0000
0.9000 5.5000
0.9500 10.5000
0.9800 25.5000
0.9900 50.5000
⎟
⎠
⎞
⎜
⎝
⎛
−
+=
α1
11
2
1)(nC
Vantagens e Desvantagens da
Transformação da Chave
30
} Vantagens
} Alta eficiência no custo de pesquisa, que é O(1) para o
caso médio.
} Simplicidade de implementação.
} Desvantagens
} Pior caso é O(N).
AEDSII_aula_022_hashing2.pdf
Pesquisa em memória
primária: hashing
Algoritmos e Estruturas de Dados II
Hashing Dinâmico
2
} Evita que o fator de carga fique muito alto (N/M)
} Ideia: dobra o tamanho da tabela
hashing quando fator de carga passa
de um limiar.
α = N / M C(n)
0.1000 1.0556
0.2000 1.1250
0.3000 1.2143
0.4000 1.3333
0.5000 1.5000
0.6000 1.7500
0.7000 2.1667
0.8000 3.0000
0.9000 5.5000
0.9500 10.5000
0.9800 25.5000
0.9900 50.5000
void expande(TipoPesos p, TipoDicionario T) {
T2 = NovoHeap(2 * M);
for (i = 0; i < M; i++)
if (((strcmp(T[i].Chave, Vazio) != 0) &&
(strcmp(T[i].Chave, Retirado) != 0)
InsereHashing(T[i].Chave,p,T2);
}
/* libera a memória para T */
Hashing Duplo
3
} Mecanismo para resolução de colisão
} Endereçamento aberto apresenta o efeito de
agrupamento
} Agrupa chaves próximas a um endereço, mesmo que a
função de espalhamento não a coloque lá.
} Solução: hashing duplo
} Ao invés de examinar cada uma das posições sucessivas
após uma colisão, uma segunda função de hashing é aplicada.
Hashing Duplo
4
Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T) {
unsigned int i=0, count = 0;
unsigned int Inicial, segundo;
Inicial = h(Ch, p); /* transforma a chave */
segundo = h2(Inicial); /* h2(x) = ((x%97)+1) */
while ((strcmp(T[(Inicial + i) % M].Chave, Vazio) != 0) &&
(strcmp(T[(Inicial + i) % M].Chave, Ch) != 0) &&
(count < M)) {
i += segundo; count++;
}
if (strcmp(T[(Inicial + i) % M].Chave, Ch) == 0)
return ((Inicial + i) % M);
else
return M; /* Pesquisa sem sucesso */
}
Hashing Duplo: Análise
5
α = N / M C(n)
0.1000 1.0536
0.2000 1.1157
0.3000 1.1889
0.4000 1.2771
0.5000 1.3863
0.6000 1.5272
0.7000 1.7200
0.8000 2.0118
0.9000 2.5584
0.9500 3.1534
0.9800 3.9919
0.9900 4.6517
⎟
⎠
⎞
⎜
⎝
⎛
−
=
α
ln
α
)n(C
1
11
Hashing Duplo: Análise
6
Hashing
duplo
Endereçamento
aberto linear
α = N / M C(n) C(n)
0.1000 1.0536 1.0556
0.2000 1.1157 1.1250
0.3000 1.1889 1.2143
0.4000 1.2771 1.3333
0.5000 1.3863 1.5000
0.6000 1.5272 1.7500
0.7000 1.7200 2.1667
0.8000 2.0118 3.0000
0.9000 2.5584 5.5000
0.9500 3.1534 10.5000
0.9800 3.9919 25.5000
0.9900 4.6517 50.5000
⎟
⎠
⎞
⎜
⎝
⎛
−
+=
α1
11
2
1)(nC
Endereçamento aberto:
Hashing duplo:
⎟
⎠
⎞
⎜
⎝
⎛
−
=
α
ln
α
)n(C
1
11
Hashing Perfeito
7
} Uma função de espalhamento h é perfeita se
h(xi) ≠ h(xj) para todo i ≠ j
} Desta maneira, não haverá colisões de chaves.
} Problema:
} Quando chaves adicionais foram adicionadas, colisões
poderão ocorrer.
} Indicações de uso:
} Conjunto de chaves seja estático e frequentemente
pesquisado. Exemplo: palavras-chave de um compilador
Hashing Perfeito
8
} Definição anterior permite que tabelas grandes sejam
utilizadas (M >> N), o que não economiza muito
espaço de armazenamento.
} Além de perfeita, idealmente uma função de
espalhamento deve ser mínima. Se há N chaves,
tem-se uma tabela de espalhamento com N posições.
Hashing Perfeito
9
} Encontrando uma função de hashing perfeita
} Abordagens:
} Funções de espalhamento perfeitas por redução do
quociente
} h(x) = (x + s) / d (para inteiros s e d)
} Funções de espalhamento perfeitas por redução de resto
} h(x) = ((r + s * x) % z) / d
} Espalhamento recíproco – espalhamento perfeito e mínima
} h(x) = (c / (d * x + e)) % M
} Quando chaves são primos entre si: h(x) = (c / x) % M
Exercícios
10
} Mostre
o
estado
final
de
um
dicionário
com
resolução
de
conflitos
por
encadeamento
depois
da
inserção
das
chaves
q
u
e
s
t
a
o
f
c
i
l.
Considere
que
o
dicionário
não
armazena
chaves
duplicadas,
que
o
valor
de
cada
caractere
é
sua
ordem
no
alfabeto
e
que
o
dicionário
possui
uma
tabela
com
5
listas
(isto
é,
M
=
5).
} Mostre o conteúdo de um dicionário com resolução de
conflitos com endereçamento aberto depois da inserção
das chaves q u e s t a o f c i l. Considere que a tabela do
dicionário tem 17 posições e que o valor de cada
caractere é sua ordem no alfabeto.
AEDSII_aula_023_pesquisa_digital.pdf
Pesquisa digital
Algoritmos e Estruturas de Dados II
Pesquisa digital
} A pesquisa digital usa a representação das chaves para
estruturar os dados na memória
} Por exemplo, a representação de um número em binário
} A representação de um string com uma sequência de
caracteres
} A pesquisa digital está para árvores binárias de pesquisa
como radixsort está para os métodos de ordenação
} Pesquisa não é baseada em comparação de chaves, mas sim em
processamento feito sob a chave
Trie binária
} Cada nó no nível i representa o conjunto de todas as
chaves que começam com a mesma sequência de i bits
} Cada nó tem duas ramificações, uma para as chaves cujo
bit (i+1) é zero e outra para chaves cujo bit (i+1) é um
Trie binária – exemplo de pesquisa
} Busca em uma trie binária é parecida com pesquisa em
árvore de busca
} Mas não comparamos chaves
} Percorremos a trie de acordo com os bits da chave
Q
Trie – estruturas
struct no {
struct no *esq;
struct no *dir;
struct registro *reg;
};
struct registro {
int chave;
/* outros dados */
};
Trie binária – pesquisa
struct registro *pesquisaR(struct no *t, int chave, int p) {
if(t == NULL) return NULL;
if(t->esq == NULL && t->dir == NULL) {
int regchave = t->reg->chave;
if (regchave == chave) { return t->reg; }
else { return NULL; }
}
if(digito(chave, p) == 0) { /*busca sub-árvore esquerda */
return pesquisaR(t->esq, chave, p+1); }
else { /* busca sub-árvore direita */
return pesquisaR(t->dir, chave, p+1); }
}
struct registro *pesquisa(struct no *trie, int chave){
return pesquisaR(trie, chave, 0);
}
Trie binária – exemplo de inserção
} Fazemos uma pesquisa na árvore para descobrir onde a
chave será inserida
} Primeiro caso: se o nó externo onde a pesquisa terminar for
vazio, basta cria um novo nó para conter a nova chave
} Inserindo W = 110110
Q
Trie binária – exemplo de inserção
} Fazemos uma pesquisa na árvore para descobrir onde a
chave será inserida
} Segundo caso: se o nó externo onde a pesquisa terminar
tiver uma chave, criamos nós internos até encontrar o bit onde
a nova chave difere da chave já existente
} Inserindo K = 100010
Q
Trie – exemplo de inserção
Q
W = 110110
K = 100010
Trie – inserção
struct no *insereR(struct no *t, struct registro *reg, int p){
int chave = reg->chave;
if(t == NULL) return cria_trie(reg);
if(t->esq == NULL && t->dir == NULL) {
return separa(cria_trie(reg), t, p);
}
if(digito(chave, p) == 0) /* insere sub-árvore esquerda */
t->esq = insereR(t->esq, reg, p+1);
else /* insere na sub-árvore direita */
t->dir = insereR(t->dir, reg, p+1);
return t;
}
void insere(struct no **trie, struct registro *reg) {
*trie = insereR(*trie, reg, 0);
}
Trie – inserção
struct no *separa(struct no *no1, struct no *no2, int p){
novo = cria_trie(NULL);
int chave1 = no1->reg->chave;
int chave2 = no2->reg->chave;
if(digito(chave1, p) == 0 && digito(chave2, p) == 0){
novo->esq = separa(no1, no2, p+1);
} else if(/* chave1 == 0 && chave2 == 1 */) {
novo->esq = no1; novo->dir = no2;
} else if(/* chave1 == 1 && chave2 == 0 */) {
novo->dir = no1; novo->esq = no2;
} else if(/* chave1 == 1 && chave2 == 1 */) {
novo->dir = separa(no1, no2, p+1);
}
return novo;
}
Vantagens
} O formato das tries não depende da ordem em que as
chaves são inseridas
} Depende apenas dos valores das chaves
} Inserção e busca numa trie com N chaves aleatórias
requer aproximadamente lg(N) comparações de bits no
caso médio
} O pior caso é limitado pelo número de bits das chaves
Desvantagens
} Caminhos de uma única direção acontecem quando
chaves compartilham vários bits em comum
} Por exemplo, as chaves B (00010) e C (00011) são idênticas
exceto no último bit
} Requer inspeção de todos os bits da chave independente do
número de registros na trie
} Os registros são armazenados apenas nas folhas, o que
desperdiça memória em nós intermediários
} Uma trie com N registros tem aproximadamente 1.44N nós
Patricia
} Practical Algorithm To Retrieve Information Coded in
Alphanumeric
} Criada por Morrison 1968 para recuperação de
informação em arquivos de texto
} Estendido por Knuth em 73, Sedgewick em 88, Gonnet e
Baeza-Yates em 91
Patricia
} Patricia usa o conceito de pesquisa digital, mas estrutura
os dados de forma a evitar as desvantagens citadas das
tries
} Remove caminhos de única direção
} Evita o desperdício de memória em nós internos
} Cada nó da árvore contém uma chave e um índice
indicando qual bit deve ser testado para decidir qual ramo
seguir
Patricia – exemplo de pesquisa
RH
S
E
C
A
0
3
2
1
4
4
Busca por
R = 10010
I = 01001
Patricia – estruturas
struct no {
struct no *esq;
struct no *dir;
int bit;
struct registro *reg;
};
struct registro {
int chave;
/* outros dados */
};
Patricia – pesquisa
struct registro *pesquisaR(struct no *t, int chave,int bit)
{
if(t->bit <= bit) return t;
if(digito(chave, t->bit) == 0) {
return pesquisaR(t->esq, chave, t->bit);
}
else {
return pesquisaR(t->dir, chave, t->bit);
}
}
struct registro *pesquisa(struct no *pat, int chave) {
struct registro *reg;
reg = pesquisaR(pat->esq, chave, -1);
if(reg->chave == chave) { return reg; }
else { return NULL; }
}
Patricia – exemplo de inserção
RH
S
E
C
A
0
3
2
1
4
4
Inserindo
I = 01001
H = 01000
Patricia – exemplo de inserção (caso 1)
RH
S
E
C
A
0
3
2
1
4
4
I
4
Inserindo
I = 01001
H = 01000
Primeiro bit que diferencia
chaves não foi utilizada na busca
Patricia – exemplo de inserção
RH
S
E
C
A
0
3
2
1
4
4
Inserindo
N = 01110
I = 01001
I
4
Patricia – exemplo de inserção (caso 2)
RH
S
E
C
A
0
3
2
1
4
4
N
2
I
4
Inserindo
N = 01110
I = 01001
Primeiro bit que diferencia
chaves foi pulado na busca
Casos
da Inserção
} Caso 1: O novo nó substitui um nó externo
} Acontece quando o bit que diferencia a nova chave da chave
encontrada não foi utilizado na busca
} Caso 2: O novo nó substitui um nó interno
} Acontece quando o bit que diferencia a nova chave da chave
encontrada foi pulado durante a busca
struct no *inicializa() {
struct no *novo;
novo = cria_pat(NULL, -1);
novo->esq = novo->dir = novo;
return novo;
}
Patricia – inserção
void insere(struct no *pat, struct registro *reg) {
int chave = reg->chave;
struct registro *ins;
int ichave;
int i = 0;
ins = pesquisaR(pat->esq, chave, -1);
ichave = ObtemChave(ins); /* 0 se não há chaves */
if (chave == ichave) return; /* chave já existe */
/* procura pelo bit diferenciador */
while (digito(chave, i) == digito(ichave, i)) i++;
/* i é o bit diferenciador */
pat->esq = insereR(pat->esq, reg, i, pat);
}
Patricia – inserção
struct no *insereR(struct no *t, struct registro *reg,
int bit, struct no *pai) {
int chave = reg->chave;
if((t->bit >= bit) || (t->bit <= pai->bit)) {
struct no *x = cria_pat(reg, bit);
x->esq = digito(chave, x->bit) ? t : x;
x->dir = digito(chave, x->bit) ? x : t;
return x;
} else if (digito(chave, t->bit) == 0) {
t->esq = insereR(t->esq, reg, bit, t);
} else {
t->dir = insereR(t->dir, reg, bit, t);
}
return t;
}
Considerações
} Inserção numa árvore patricia com N chaves aleatórias
requer aproximadamente lg(N) comparações de bits no
caso médio e 2lg(N) comparações no pior caso
} O número de comparações de bits é limitado pelo
tamanho das chaves
} Não existe desperdício de memória nos nós internos
Exercícios
} Implemente as funções
} struct no * cria_trie(struct registro *reg);
} struct no * cria_pat(struct registro *reg, int bit);
} Mostre a trie resultante da inserção das chaves E X M P L
O F A
E: 00101 X: 11000 M: 01101 P: 10000
L: 01100 O: 01111 F: 00110 A: 00001
Exercícios
} Implemente as funções
} struct no * cria_trie(struct registro *reg);
} struct no * cria_pat(struct registro *reg, int bit);
} Mostre a trie resultante da inserção das chaves E X M P L
O F A
} Mostre a árvore patricia resultante da inserção das chaves
E X M P L O F A
E: 00101 X: 11000 M: 01101 P: 10000
L: 01100 O: 01111 F: 00110 A: 00001
Tries M-árias
} Apresentamos apenas tries binárias mas podemos ter tries
M-árias
} Cada filho corresponde a um possível valor do
i-ésimo “bit”
} Por exemplo, cada nó numa trie para armazenar strings pode
ter 256 filhos (um pra cada valor possível para um caractere)
Solucao Aulas 07, 08 e 09.pdf
Universidade Federal de Minas Gerais
Departamento de Ciência da Computação
Algoritmos e Estruturas de Dados II
2º Semestre de 2011
Solução dos Exercícios Aula 07, 08 e 09.pdf
1.
•••• A função p1 calcula a multiplicação da matriz A pela matriz B e coloca o resultado na matriz C.
•••• A operação relevante é o número de operações de multiplicação e soma realizadas com os elementos
dos vetores.
∑∑∑
−
=
−
=
−
=
===
1
0
1
0
1
0
32...2)(
n
i
n
j
n
k
nnT
)()( 3nOnT =
2. A função p2 calcula o seguinte somatório:
∑∑
= =
+
===
n
i
n
ij
nn
x
1
2
2
...1
∑∑
=
−
=
−
===
n
i
i
j
nny
1
21
1 2
...1
Considerando que a operação relevante seja o número de operações de soma realizadas com as variáveis x
e y:
∑ ∑ ∑
= =
−
=
==
+=
n
i
n
ij
i
j
nnT
1
2
1
1
...11)(
)()( 2nOnT =
3.
Vamos analisar as listas de comandos dentro do IF e do ELSE para verificar qual delas executa o maior
número de operações.
IF
1...1)(
1
1
−−=== ∑
−
+=
innT
n
ij
ELSE
111)(
1
0
+=+= ∑
−
=
nnT
n
j
Portanto, o pior caso será alcançado quando os comandos do ELSE forem sempre executados, ou seja,
quando todos os elementos de x forem menores ou iguais a 10. Neste caso,
∑
−
=
+==+=
1
0
2
...)1()(
n
i
nnnnT
4.
int exprec(int n) {
if (n<=0)
return(1);
else
return(2*(exprec(n-1)));
}
5. Retorna o máximo divisor comum dos números a e b.
6.
a) nnT log)( =
b) nnnT log)( =
c)
2
13)( −= nnT
7.
==
=
2loglog 42
)(
nnn
nnf
a
b
( )12−= nOn
( )nOn =
( )2)( nnT Θ=
Solucao exercicios aulas 5 e 6.pdf
Universidade Federal de Minas Gerais
Departamento de Ciência da Computação
Algoritmos e Estruturas de Dados II
2º Semestre de 2011
Solução dos Exercícios Aula 05 e 06.pdf
1.
1 seg. 1 min. 1 hora 1 dia 1 mês 1 ano 1 século
log n 2 1,1 x 1018 101.084 1026.009 10780.270 109.493.282 10949.328.194
n 1 3,6 x 103 1,2 x 107 7,4 x 109 6,7 x 1012 9,9 x 1014 9,9 x 1018
n 1 6 x 10 3,6 x 103 8,6 x 104 2,6 x 106 3,2 x 107 3,2 x 109
n log n 1 15 414 6.787 150.687 1,5 x 106 1,2 x 108
n2 1 7 60 293 1.609 5.615 56.156
n3 1 3 15 44 137 315 1.466
2n 0 5 11 16 21 24 31
n! 1 4 6 8 9 10 12
2.
q: probabilidade pesquisa com sucesso
1-q: probabilidade pesquisa sem sucesso
Nas pesquisas com sucesso, cada registro tem a mesma probabilidade de ser acessado.
pi: probabilidade de que o i-ésimo registro seja o procurado
pi = q/n
Número de comparações das pesquisas sem sucesso = n. Portanto,
T(n) = 1 (q/n) + 2 (q/n) + 3 (q/n) + ... + n (q/n) + n (1-q) = ... = (2n+q-nq)/2
3.
a) Operação relevante é o número de vezes que a operação soma é realizada
2
2
1
3...3)( nnT
i
n
ij
j
ik
===∑∑∑
= = =
b)
Operação relevante é o número de comparações com os elementos do vetor
Pior caso:
∑
=
−+===
n
j
nnjnT
2
2
1
22
...)(
Melhor caso:
1...1)(
2
−===∑
=
nnT
n
j
Operação relevante é o número de movimentações com os elementos de A
Pior caso:
( )∑
=
−+==+=
n
j
nnjnT
2
2
3
2
5
2
...2)(
Melhor caso:
33...3
2
−==∑
=
n
n
j
c)
Operação relevante é o número de comparações com os elementos do vetor
∑∑
= +=
−===
n
i
n
ij
nn
nT
1 1
2
22
...1)(
Operação relevante é o número de movimentações com os elementos do vetor.
Pior caso:
∑∑
= +=
−===
n
i
n
ii
nnnT
1
2
1 2
3
2
3
...3)(
Melhor caso:
T(n)=0
d)
Operação relevante é o número de comparações com a chave
∑∑
−
= +=
−===
1
1 1
2
22
...1)(
n
i
n
ij
nn
nT
Operação relevante é o número de movimentações com a chave
∑
−
=
−===
1
1
)1(3...3)(
n
i
nnT
4.
Vamos tentar provar que 6n3 = Θ(n2). Para isso devemos achar constantes 01 >c , 02 >c e 00 >n , tal
que:
0
2
2
32
1 ;6 nnncnnc ≥∀≤≤
Dividindo por n2, temos:
021 ;6 nncnc ≥∀≤≤
⇒≥⇒≤ nccn 66 22 Impossível, pois não existe constante que possa ser maior
ou igual a 6n para todo n
maior ou igual a 0n .
Portanto, 6n3 ≠ Θ(n2)Mais conteúdos dessa disciplina
Introdução ao Estudo da Biologia- SubjectControllerTest_getMaterialsByFilter
- updateOrder 0 0 1
- Captura de Tela 2023-06-20 as 10 19 58
- updateOrder 0
- Documento sem titulo
- Prova Prefeitura Municipal de Igarapé-Miri - FUNDAÇÃO DE AMPARO E DESENVOLVIMENTO DA - 2009 - para Fisioterapeuta.pdf
- Material - 2
- Material - 1
- Material - 2
- Material - 2
- png-format
- Can't Tell Me Nothing with Zach Galifianakis - High Quality Video
- giardia
- Princípios de Geomecânica - parte 7
Mais conteúdos dessa disciplina
- Introdução ao Estudo da Biologia
- SubjectControllerTest_getMaterialsByFilter
- updateOrder 0 0 1
- Captura de Tela 2023-06-20 as 10 19 58
- updateOrder 0
- Documento sem titulo
- Prova Prefeitura Municipal de Igarapé-Miri - FUNDAÇÃO DE AMPARO E DESENVOLVIMENTO DA - 2009 - para Fisioterapeuta.pdf
- Material - 2
- Material - 1
- Material - 2
- Material - 2
- png-format
- Can't Tell Me Nothing with Zach Galifianakis - High Quality Video
- giardia
- Princípios de Geomecânica - parte 7
