Complexidade de Algoritmos
! 
Uma característica importante de qualquer
algoritmo é seu tempo de execução
!  é possível determiná-lo através de métodos
empíricos, considerando-se entradas diversas
!  é também possível obter este tempo a partir
de métodos analíticos
1
Complexidade de Algoritmos
! 
Métodos analíticos
!  objetivo: determinar uma expressão
matemática que traduza o comportamento
de tempo de um algoritmo.
!  o tempo de execução independente:
! 
! 
! 
do método utilizado
da linguagem e compiladores empregados
e das condições locais de processamento
2
Complexidade de Algoritmos
! 
! 
obter uma expressão matemática não é
simples, mesmo considerando uma expressão
aproximada
Várias simplificações são introduzidas
!  quantidade de dados a serem manipulados
pelo algoritmo é suficientemente grande
!  quantidade de dados de entrada reduzida
não serão considerados
3
Complexidade de Algoritmos
! 
! 
somente o comportamento assintótico é
avaliado
não serão consideradas constantes aditivas
ou multiplicativas na expressão considerada
4
Complexidade de Algoritmos
! 
Qual a variável em relação à qual a expressão
matemática avaliará o tempo de execução?
! 
! 
Um algoritmo funciona a partir de uma entrada para
produzir uma saída dentro de um tempo
fornecer o tempo de execução em função da entrada
5
Complexidade de Algoritmos
! 
O processo de execução de um algoritmo pode
ser dividido em etapas elementares - passos
!  um número fixo de operações básicas cujo
tempo de execução é considerado constante
!  a operação básica de maior freqüência de
execução do algoritmo é denominada
operação dominante
6
Complexidade de Algoritmos
! 
expressão de tempo de execução
! 
! 
obtida a menos de constantes aditivas e multiplicativas:
número de passos
! 
! 
≅ número de execuções da operação dominante
A expressão matemática de avaliação do tempo de
execução de um algoritmo
! 
função que fornece o número de passos efetuados no algoritmo
a partir de uma certa entrada
7
Complexidade de Algoritmos
! 
Por exemplo: algoritmos para ordenar
elementos de uma seqüência dada
! 
! 
os
cada passo corresponde a comparação entre dois
elementos da seqüência
O número de passos de um algoritmo
! 
informação
necessária
comportamento no tempo
para
avaliar
8
seu
Complexidade de Algoritmos
! 
Inversão de uma seqüência
fim = n/2;
for (i=0; i<fim; i++)‫‏‬
{
temp = S[i];
S[i] = S[n-1-i];
S[n-1-i] = temp;
}
9
Complexidade de Algoritmos
! 
n = 5 ⇒ troca S[i] por S[n-1-i]
fim = 2
!  i = 0 ⇒ troca S[0] por S[5-1-0] (S[4])‫‏‬
!  i = 1 ⇒ troca S[1] por S[5-1-1] (S[3])‫‏‬
! 
inicial
0
1
final
2
3
4
0
1
2
3
M A R
I
A
A I
R
A M
10
4
Complexidade de Algoritmos
! 
n = 6 ⇒ troca S[i] por S[n-1-i]
! 
! 
! 
! 
fim = 3
i = 0 ⇒ troca S[0] por S[6-1-0] (S[5])‫‏‬
i = 1 ⇒ troca S[1] por S[6-1-1] (S[4])‫‏‬
i = 2 ⇒ troca S[2] por S[6-1-2] (S[3])‫‏‬
inicial
final
0
1
2
3
4 5
E
S
T
A D O
0
1
2
O D A
3
4
5
T S
E
11
Complexidade de Algoritmos
! 
n = 50 ⇒ troca S[i] por S[n-1-i]
fim = 25
!  i = 0 ⇒ troca S[0] por S[50-1-0] (S[49])‫‏‬
!  i = 1 ⇒ troca S[1] por S[50-1-1] (S[48])‫‏‬
!  i = 2 ⇒ troca S[2] por S[50-1-2] (S[47])‫‏‬
.........
!  i = 23 ⇒ troca S[23] por S[50-1-23] (S[26])‫‏‬
!  i = 24 ⇒ troca S[24] por S[50-1-24] (S[25])‫‏‬
! 
12
Complexidade de Algoritmos
! 
o algoritmo executa extamente as mesmas
operações para seqüências de tamanho n
!  cada passo corresponde à troca de posição
entre dois elementos da seqüência
! 
! 
a execução das três atribuições
o número de passos é igual ao número de
vezes que executa o bloco for ⇒ n/2, n>1
13
Complexidade de Algoritmos
! 
Problema: determinar a soma C e o produto
D de duas matrizes dadas A e B.
A = (aij) e B = (bij) ambas n x n
!  C e D também serão matrizes n x n
!  seus elementos podem ser calculados como:
⇒ cij = aij + bij
! 
⇒ dij = ∑aik * bkj
1≤k ≤ n
14
Complexidade de Algoritmos
! 
Soma
for(i=0; i<n; i++)‫‏‬
for(j=0; j<n; j++)‫‏‬
cij = aij + bij ;
! 
Produto
for(i=0; i<n; i++)‫‏‬
for(j=0; j<n; j++){
dij = 0;
for(k=0; k<n; k++)
dij = dij + aik* bkj;
}
15
Complexidade de Algoritmos
! 
Seja A um algoritmo
! 
! 
{E1, ....Em} o conjunto de todas as entradas
possíveis de A
seja ti o número de passos efetuados por A
quando a entrada for Ei
16
Complexidade de Algoritmos
! 
Complexidade do pior caso:
max
! 
{ti }
Complexidade do melhor caso:
min
! 
Ei ∈ E
{ti }
Ei ∈ E
Complexidade do caso médio:
Σ
! 
1≤i ≤ m
piti
pi é a probabilidade de ocorrência da entrada Ei
17
Complexidade de Algoritmos
! 
De forma análoga podem ser definidas
complexidades de espaço de um algoritmo
! 
complexidade tem por objetivo avaliar a eficiência
de tempo ou espaço
18
Complexidade de Algoritmos
! 
Complexidade de tempo do pior caso
! 
para a entrada mais desfavorável
! 
é a mais importante das três mencionadas
! 
fornece um limite superior para o número de
passos
19
Complexidade de Algoritmos
! 
Complexidade de pior caso
! 
Complexidade de melhor caso
! 
! 
de uso bem menos freqüente
! 
em algumas situações específicas
Complexidade de caso médio
! 
! 
menos utilizada apesar de importante
difícil conhecer a distribuição de probabilidades
das diferentes entradas
20
Recursividade
! 
! 
um procedimento recursivo é aquele que contém
uma ou mais chamadas a si mesmo
a todo procedimento recursivo corresponde um não
recursivo
! 
os programas recursivos são mais concisos
! 
relação direta com a prova por indução matemática
21
Recursividade
! 
Cálculo de fatorial
x! = se (x <=0) então 1 senão x * (x-1)!
22
Recursividade
Implementação não recursiva
x! = se x <=0 1 senão x * (x-1)!
int fatorial (int N)‫‏‬
{
int result = 1;
for (i=1; i<=N; i++)‫‏‬
result = result * i;
return (result);
}
23
Recursividade
Implementação recursiva
x! = se x <=0 1 senão x * (x-1)!
int fatorial (int N)‫‏‬
{
if (N<= 1)‫‏‬
return(1);
else
return( N * fatorial(N-1));
}
24
Recursividade
! 
X= fatorial (4)‫‏‬
return(
!  return(
!  return(
!  return(
! 
4* fatorial(3) )‫‏‬
3* fatorial(2) )‫‏‬
2* fatorial(1) )‫‏‬
1 )‫‏‬
25
Análise de Recursividade
! 
relação de recorrência
! 
! 
a função é definida em termos dela própria, recursivamente
substituição repetida
int fatorial (int N)‫‏‬
{
if (N<= 1)‫‏‬
return(1);
else
return( N * fatorial(N-1));
}
26
Análise de Recursividade
int fatorial (int N)‫‏‬
{
if (N<= 1)‫‏‬
return(1);
else
return( N * fatorial(N-1));
}
27
Análise de Recursividade
T(n)‫‏‬
! 
! 
tempo de processar o algoritmo para entrada n
número de passos ou operações dominantes
Fatorial
T(n) = 1,
= T(n-1) + 1,
mas quanto é T(n-1) ?
se n = 0
se n > 0
int fatorial (int N)‫‏‬
{
if (N<= 1)‫‏‬
return(1);
else
return( N * fatorial(N-1));
}
28
T(n) - Fatorial
Passos
= (T(n-1)) + 1
iteração
- 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2
29
T(n) - Fatorial
Passos
= (T(n-1)) + 1
iteração
- 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2
- 2ª substitição
= (T(n-3) + 1) + 2
= T(n-3) + 3
30
T(n) - Fatorial
Passos
= (T(n-1)) + 1
iteração
- 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2
- 2ª substitição
= (T(n-3) + 1) + 2
= T(n-3) + 3
- 3ª substituição
31
T(n) - Fatorial
Passos
= (T(n-1)) + 1
iteração
- 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2
- 2ª substitição
= (T(n-3) + 1) + 2
= T(n-3) + 3
- 3ª substituição
.....
....
= T(n-k) + k
- k-ésima substituição
32
T(n) - Fatorial
! 
! 
Então, T(n) = T(n-k) + k, 1 ≤ k ≤ n
se a k-ésima interação é a última, então:
! 
n-k = 0 e T(0) = 1
! 
Assim, n = k, e T(n) = n + 1
33
Maior elemento de uma lista
maior = a[0];
for ( i =0; I < N; i++)‫‏‬
if (maior < a[i]) maior = a[i];
return (maior);
34
Resolva as recorrências
! 
T(n)
! 
T(n)
! 
T(n)
=
=
=
=
=
=
1,
2 T(n-1) + 1,
1
T(n/2) + 1
1
2T(n/2) - n
se
se
se
se
se
se
35
n=0
n >0
n=1
n>1
n=1
n>1
Qual melhor algoritmo?
! 
! 
Sejam A e B dois algoritmos que o resolvem o
problema P, cujos tempos de execução são
TA(n) e TB(n)
comportamento assintótico – tamanho da
entrada arbitrariamente grande
! 
caracterizado pela notação O (big O)‫‏‬
36
A notação
! 
Ο
Sejam f(n) e h(n) funções reais não negativas
da variável inteira n ≥ 0
!  f(n)
= O (h(n)) quando existir uma
constante c> 0 e um valor inteiro no tal
que
n > no ⇒ f(n) ≤ c.h(n)‫‏‬
37
A notação
Ο
f(n) = 8n + 128 ⇒ é O (n2)?
f(n) ≤ c.n2 ?
!  Seja c =1
8n + 128 ≤ n2, então
0 ≤ n2 – 8n – 128
0 ≤ (n – 16)(n+8) ⇒ n0 = 16
⇒ c =1, no = 16, f (n) ≤ c.n2 para todo n ≥ n0
38
A notação
! 
! 
Ο
Tempo (ou espaço) é contabilizado em número de
passos do algoritmo (unidade de armazenamento)‫‏‬
Análise do algoritmo determina uma função que
depende do tamanho da entrada n.
10n3 + 4n -10
!  à medida que n aumenta, o termo cúbico começa
a dominar
!  A constante do termo cúbico tem relativamente a
mesma importância que a velocidade da CPU
39
A notação
! 
Ο
Complexidade de pior caso
! 
desprezar constantes aditivas ou multiplicativas
! 
! 
número de passos 3n será aproximado para n
interesse assintótico: termos de menor grau
podem ser desprezados:
! 
! 
n2 + n será aproximado para n2
6n3 + 4n - 9 será aproximado para n3
40
A notação
! 
Ο
A função atua como um limite
assintótico da função f
2
!  f = n -1
⇒
2
!  f = n -1
⇒
!  f = 403
⇒
2
!  f = 5+2logn +3log n
⇒
2
!  f = 5+2 log n +3log n ⇒
n
10
!  f = 5.2 +5n
⇒
superior
f
f
f
f
f
f
=
=
=
=
=
=
41
Ο(n2)‫‏‬
Ο(n3)
Ο(1)‫‏‬
Ο(log2n)‫‏‬
Ο(n)‫‏‬
Ο(2n)‫‏‬
A notação
! 
! 
! 
Ο
g(n), h(n) - funções reais positivas
k - constante
f1(n) = g(n) e f2(n) = h(n)
O(g+h) = O(g) + O(h)‫‏‬
!  O(k*g) = k O(g) = O(g)‫‏‬
!  f1(n) + f2(n) = O(max {g(n), h(n)})‫‏‬
!  f1(n) * f2(n) = O(g(n) * h(n))‫‏‬
! 
42
A notação
! 
Ο
O algoritmo de inversão de uma seqüência:
! 
! 
! 
o número de passos se mantém o mesmo para o
mesmo valor de n
variável independente é n
as complexidades de pior, melhor e pior casos são
iguais
43
A notação
! 
Para a inversão
! 
! 
Ο
efetua sempre n/2 passos então sua
complexidade é Ο(n)‫‏‬
Para a soma e o produto de matrizes n x n
verifica-se complexidades
2
3
!  Ο(n ) e Ο(n ) respectivamente
44
A notação
! 
Ο
Para procedimentos recursivos pode-se
aplicar a seguinte técnica
!  determina-se o número total de chamadas
ao procedimento recursivo
!  calcula-se a complexidade de execução de
uma única chamada
!  complexidade
número de chamadas × complexidade de uma chamada
45
A notação
! 
Ο
por outro lado, um outro exemplo:
!  duas matrizes A e B de dimensões n x n
!  um parâmetro x, com valores 0 ou 1
!  dependendo do valor de x
! 
! 
calcula a soma: se x =0 " A + B
ou o produto das matrizes: se x = 1" A * B
46
A notação
! 
! 
entrada: n2+1 informações - tamanho O(n2)
se x =0 então complexidade: O(n2)‫‏‬
! 
! 
Ο
complexidade do melhor caso
se x = 1 então complexidade: O(n3)
! 
complexidade do pior caso
47
Alguns conceitos
! 
! 
! 
! 
! 
! 
! 
! 
T
T
T
T
T
T
T
T
(n)
(n)
(n)
(n)
(n)
(n)
(n)
(n)
=
=
=
=
=
=
=
=
O
O
O
O
O
O
O
O
(1) : constante
(log log n) : super-rápido
(log n) : logarítmico – muito bom
(n) : linear – toda a entrada é visitada
(n log n) : limite de muitos problemas
(n2) : quadrático
(nk) : polinomial no tamanho da entrada
(kn), O (n!), O (nn) : exponencial – ruim!
48