Análise da Complexidade
ƒ Objetivos
– identificar uma expressão matemática para analisar e
comparar os comportamentos assintótico de funções
ou algoritmos
– este conceito é empregado normalmente para
analisar os tempos de execução de algoritmos, mas
pode ser também usado na análise dos espaços de
memória utilizados.
Complexidade de Algoritmos
Renê Pegoraro
ƒ A expressão matemática que define a
complexidade de um algoritmo é determinada
pela contagem de uma grandeza (por exemplo,
as operações realizadas).
Expressão que define a
Complexidade
A Notação do O-Grande
ƒ Representada por uma expressão matemática
ƒ Esta expressão é definida utilizando uma variável que
representa o número de instruções dominantes
executadas.
ƒ Operação dominante
ƒ Essência da notação do grande O:
– ordem de grandeza do comportamento assintótico de
uma função.
ƒ f é O(g)
– conjunto de operações básicas que são executadas repetidas
vezes.
– f é um grande O de g, se existe uma
constante K, tal que:
f(n) ≤ Kg(n) para qualquer n ≥ M
ƒ Formas de caracterização
– Pelo pior caso (O) Ö procura-se definir um limite superior da
complexidade.
– Pelo caso médio (Θ) Ö pretende-se obter uma caracterização
da complexidade para situações típicas. Freqüentemente a
caracterização do caso médio é problemática e necessita de
uma análise estatística.
– Pelo caso melhor (Ω) Ö pouco usada, pois representa apenas
casos específicos e não representativos.
sendo K e M inteiros positivos fixos.
ƒ g é um limite assintótico superior para
argumentos da função f
http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/MasterInfo/Cours/grandO.html
A Notação do O-Grande
A Notação do O-Grande
ƒ Por exemplo:
ƒ Considera o pior caso para o número de
operações executadas
ƒ Simplificações empregadas:
– Considerando as funções f e g definidas por:
f(n) = 10n e g(n) = n2
• a relação f = O(g) é verificada
• abaixo a tabela dos primeiros valores de f e g
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
f(n)
0
10
20
30
40
50
60
70
80
90
100
110
120
130
0
1
4
9
16
25
36
49
64
81
100
121
144
169
g(n)
– f(n) ≤ g(n) para todos n ≥ M (M=10, K=1)
– considera-se apenas as repetições de maior
impacto;
– não considera-se constantes multiplicativas nem
aditivas na expressão matemática obtida;
– se a expressão depende de uma condicional, usa-se
a situação que resulta na maior complexidade;
– termos de grau menos são desprezados.
http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/MasterInfo/Cours/grandO.html
1
Exemplos
Exemplos – O()
ƒ Soma de matrizes:
for (i=0; i<n; i++)
for (j=0; j<n; j++)
c[i][j]=a[i][j]+b[i][j];
ƒ Número de operações: f(n) = 2n2.
Complexidade: O(n2);
ƒ Multiplicação de matrizes:
for (i=0; i<n; i++)
for (j=0; j<n; j++)
c[i][j] = 0;
for (k=0; k<n; k++)
c[i][j] = c[i][j]+a[i][k]*b[k][j];
ƒ
ƒ
ƒ
ƒ
ƒ
ƒ
f(n) = n2 – 1 = O(n2)
f(n) = n3 + 1 = O(n3)
f(n) = 123 = O(1)
f(n) = 7 + 5log n + 3log2 n = O(log2 n)
f(n) = 3n + 5log n + 2 = O(n)
f(n) = 8 * 3n + 6n7 = O(3n)
ƒ Número de operações: f(n) = 3*n3 + n2.
Complexidade: O(n3);
A Notação do Ω
ƒ f é Ω(g)
–f é um Ω de g, se existe uma constante
K, tal que:
f(n) ≥ Kg(n) para qualquer n ≥ M
sendo K e M inteiros positivos fixos.
ƒ g é um limite assintótico inferior para
argumentos da função f
Complexidade
ƒ Considera o melhor caso para o número
de operações executadas
ƒ Exemplos:
– f(n) = n2 – 1 = Ω(n2).
– f(n) = n3 + 1 = Ω(n3).
– f(n) = 7 + 5log n + 3log2 n = Ω(log n).
– f(n) = 5.3n + 6n7 = Ω(n7).
Algoritmos Ótimos
ƒ Complexidade de f(n)
complexidade
real
Ω(g(n))
Notação do Ω
Ο(g(n))
ƒ Se a complexidade de um algoritmo é a
menor possível, o algoritmo é dito ótimo.
ƒ Por exemplo
– para somar duas matrizes de n x n, a
complexidade é O(n2)
– os dados deverão ser pelo menos lidos, 2 * n2
operações, Ω(n2)
– como O(n2) = Ω(n2) Ö algoritmo ótimo!
2