An Lise De Complexidade



Tempo de processamento
 Um algoritmo que realiza uma tarefa em 10 horas

é melhor que outro que realiza em 10 dias


Quantidade de memória necessária
 Um algoritmo que usa 1MB de memória RAM é

melhor que outro que usa 1GB



Medir o tempo gasto por um algoritmo
 Não é uma boa opção
 Depende do compilador
▪ Pode preferir algumas construções ou otimizar melhor
 Depende do hardware
▪ GPU vs. CPU, desktop vs. smartphone



Estudar o número de vezes que operações são executadas



Achar o máximo de um vetor int vmax(int *vec, int n) { int i; int max = vec[0]; for(i = 1; i < n; i++) { if(vec[i] > max) { max = vec[i];
}
} return max;
}




Complexidade: f(n) = n-1
Esse algoritmo é ótimo

1 n-1 n-1
A < n-1 n-1 n-1
1



Análise de complexidade feita em função de n
 n indica o tamanho da entrada
▪ Número de elementos no vetor
▪ Número de vértices num grafo
▪ Número de linhas de uma matriz



Diferentes entradas podem ter custo diferente
 Melhor caso

 Pior caso
 Caso médio








Recuperar um registro num arquivo procurando sequencialmente
Quantos registros precisam ser processados em uma busca?
Melhor caso: f(n) = 1
Pior caso: f(n) = n
Caso médio: f(n) = (n+1)/2
 Supondo que registros procurados estão presentes

no arquivo e que registros são pesquisados com a mesma probabilidade



Problema: encontrar o valores minimo e máximo em um vetor

1
1
n-1 n-1 A < n-1 n-1 B < n-1
-

void minmax(int *vec, int n, int *min, int *max) { int i; int *min = vec[0]; int *max = vec[0]; for(i = 1; i < n; i++) { if(vec[i] < *min) {
*min = vec[i];
}
if(vec[i] > *max) {
*max = vec[i]; melhor caso: f(n) = 2(n-1)
}
pior caso: f(n) = 2(n-1)
}
} caso médio: f(n) = 2(n-1)



Se vec[i] < *min, então não precisamos checar se vec[i] > *max

1
1
n-1 n-1 A < n-1 n-1-A B < n-1-A
-

void minmax2(int *vec, int n, int *min, int *max) { int i; melhor caso: int *min = vec[0]; int *max = vec[0];
(decrescente)
for(i = 1; i < n; i++) { f(n) = n-1 if(vec[i] < *min) {
*min =