Aula 04 - Complexidade de Algoritmos

Prévia do material em texto

Complexidade de Algoritmos
ESTRUTURA DE DADOS
Evandro Alberto Zatti*
Professor
*Formação acadêmica: Mestrado em Engenharia de Produção pela Universidade Federal de Santa 
Catarina, Brasil (2002)
▪ Algoritmos eficientes
▪ Medidas de eficiência
▪ Contabilizando instruções de programas
▪ Análise assintótica
▪ Notação Grande-O
Sumário da Aula
▪ Exemplos de problemas:
▪ Pesquisar n números;
▪ Pesquisar um número em uma lista de n elementos;
▪ Multiplicar nn elementos;
Esforço de Processamento
▪ Tempo de processamento (tempo)
▪ Quantidade de memória utilizada (espaço)
▪ Custo = tempo + memória
Formas de Medir a Eficiência de um Algoritmo
▪ Pior caso: o maior número de operações utilizadas para atender 
qualquer entrada de tamanho “n”;
▪ Caso médio: no qual as entradas estariam em um ponto de 
equilíbrio
▪ Melhor caso: realiza o menor número de operações.
Casos de Medida
▪ Pegue 2 algoritmos que resolvem o mesmo problema para fazer a 
comparação.
▪ Algoritmo 1: 
f(n) = 20n + 100
▪ Algoritmo 2: 
f(n) = 2n2 + 5n
Complexidade de Tempo
n = 10
Complexidade de Tempo
n = 50
Complexidade de Tempo
Contabilizando Instruções
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
int v[TAM];
#define TAM 50
Algoritmo que procura o 
maior elemento de um 
vetor.
▪ Instruções simples: custo = 1
▪ Atribuição de valor para a variável;
▪ Acesso ao valor de uma posição do array;
▪ Comparação de 2 valores;
▪ Incremento de um valor.
▪ Declaração de variáveis: custo = 0
Regras
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
0
Custo:
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
1
Custo:
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
1 + 1
Custo:
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
1 + 1 + 2
Custo:
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
1 + 1 + 2 + 2n
Custo:
N vezes é o número de 
execuções do laço.
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
1 + 1 + 2 + 2n = 
4 + 2n
Custo:
f(n) = 2n + 4
Até aqui.
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
(2+1)n + 4
Custo:
N comparações no laço.
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
(2+1+1)n + 4
Custo:
N atribuições no laço.
Contabilizando Instruções
void main()
{
int v[TAM], x, i, n;
n = TAM;
x = v[0];
for (i = 0; i < n; i++)
if (v[i] >= x)
x = v[i];
}
1
2
3
4
5
6
f(n) = 4n + 4
Custo:
Resultado.
Notação Grande-O
▪ Big-O
▪ Custo
▪ Tempo de processamento
▪ Consumo de memória
▪ Pior caso possível 
▪ para todas as entradas de tamanho n
Notação Grande-O
Notação Grande-O
1
2
3
4
5
6
7
8
9
10
int v[TAM];
#define TAM 50
void bubble_sort()
{
int i, j, x, n = TAM-1;
for (i = n; i > 0; i--) {
for (j = 0; j < i; j++) {
if (v[j] > v[j + 1]) {
x = v[j];
v[j] = v[j + 1];
v[j + 1] = x;
}
}
}
}
Algoritmo de ordenação 
pelo método bolha.
Notação Grande-O
1
2
3
4
5
6
7
8
9
10
void bubble_sort()
{
int i, j, x, n = TAM-1;
for (i = n; i > 0; i--) {
for (j = 0; j < i; j++) {
if (v[j] > v[j + 1]) {
x = v[j];
v[j] = v[j + 1];
v[j + 1] = x;
}
}
}
}
1 + 2 + 3 + ... + (n-1) + n
Custo:
Notação Grande-O
1
2
3
4
5
6
7
8
9
10
void bubble_sort()
{
int i, j, x, n = TAM-1;
for (i = n; i > 0; i--) {
for (j = 0; j < n; j++) {
if (v[j] > v[j + 1]) {
x = v[j];
v[j] = v[j + 1];
v[j + 1] = x;
}
}
}
}
f(n) = n2
Custo:
Notação Grande-O
1
2
3
4
5
6
7
8
9
10
void bubble_sort()
{
int i, j, x, n = TAM-1;
for (i = n; i > 0; i--) {
for (j = 0; j < n; j++) {
if (v[j] > v[j + 1]) {
x = v[j];
v[j] = v[j + 1];
v[j + 1] = x;
}
}
}
}
O(n2)
Custo (notação Grande-O):
▪ Cota superior = limite superior = upper bound
▪ Cota inferior = limite inferior = lower bound
Tipos de Complexidade