Aula 2

' $

CALCULO DE COMPLEXIDADE

Jose de Siqueira

UFMG - ICEx - DCC

1o semestre de 2015

& %

' $Calculo de Complexidade

Calculo de Complexidade de Programas

• Contagem do numero de operacoes de cada tipo.

• Para isso, e preciso:

– determinar as operacoes relevantes.

– determinar o numero de vezes que essasoperacoes sao executadas

– nao se consideram sobrecargas degerenciamento de memoria ou E/S

• Em geral, estamos interessados na complexidadeno pior caso.

Jose de Siqueira 1& %



• Operacoes em sequencia: adicionam-se os custosde cada operacao.

Regras de Transformacao

T (read) → 1T (write) → 1T (a := b) → 1T (a > b)(e outros op. logicos) → 1T (a + b)(e outros op. aritmeticos) → 1T (if a then b else c) → T (a) + max(T (b),T (c))T (for i := 1 to n do ai) →

∑1≤i≤n

T (ai)

• Outros lacos: limite superior.

• Para funcoes ou procedimentos: ordem dechamada das funcoes.

• Funcoes ou procedimentos recursivos: relacoesde recorrencia.



Exemplo 1

function fat(n:integer):integer;

begin

if n = 0 then fat := 1

else fat := n ∗ fat(n-1);

end; % fat

• Operacao fundamental: ∗.• Seja T (n) o no de operacoes fundamentais:

T (0) = 0T (n) = 1 + T (n− 1), para n ≥ 1

• Resolucao da eq. de recorrencia:

T (0) = 0T (1) = 1 + T (0) = 1T (2) = 1 + T (1) = 2

...T (n) = 1 + T (n− 1) = n



Exemplo 2

. . .

const n = 1000;

type Vetor = array [1..n] of integer;

. . .

function Max(var A: Vetor): integer;

var i, aux: integer;

begin

aux := A[1];

for i:= 2 to n do

if aux < A[i] then aux := A[i];

Max := aux;

end; % Max

• Operacao fundamental: comparacao.

• Seja T (n) o no de comparacoes.

• Se A tiver n elementos, T (n) = n− 1.

• O algoritmo e otimo (tem o menor custopossıvel).




• Tres cenarios possıveis:

1. Melhor caso: menor tempo de execucao paratodas entradas possıveis de tamanho n.

2. Pior caso: maior tempo de execucao. . . Ocusto de um algoritmo nunca e maior que opior caso.

3. Caso medio (ou esperado): media dos temposde execucao. . . Supoe uma distribuicao deprobabilidades sobre o conjunto de entrada detamanho n.

Exemplo 3

• Pesquisa sequencial: encontrar uma chave dadadentre os registros de um arquivo.

• Seja f (n) o no de registros consultados:

– melhor caso: f (n) = 1.

– pior caso: f (n) = n.



Exemplo 3 - Continuacao

Calculo do caso medio

• Hipotese: todos os elementos sao distintos.

• Seja q a probabilidade de que a chave X esteja noarquivo A.

• Hipotese: Se X esta em A, todas as posicoes saoequiprovaveis.

• Notacao: Seja Dn,i, 1 ≤ i ≤ n o conjunto dedados onde X aparece na i-esima posicao.

• Dn,0 e o conjunto de dados do qual X esta ausente.

• Assim,

p(Dn,i) =q

ne

p(Dn,0) = 1− q.



• Pela analise do algoritmo, temos:

custo(Dn,i) = i e custo(Dn,0) = n

• Assim,

fmedio(n) =∑

0≤i≤np(Dn,i) ∗ custo(Dn,i)

= (1− q) · n +∑

1≤i≤ni · q

n

• Se sabemos que X esta em A, temos que q = 1 e

fmedio(n) =n + 1

2

• Se ha uma chance em duas de que X esteja em A,entao q = 1

2 e

fmedio(n) =n

2+n + 1

4=

3n + 1

4



Exemplo 4

• Calcular o maior e o menor elemento de um vetor

• Versao 1:procedure MaxMin1(var A: Vetor; var

Max, Min: integer);

var i: integer;

begin

Max := A[1];

Min := A[1];

for i := 2 to n do

begin

if A[i] > Max then Max := A[i];

if A[i] < Min then Min := A[i];

end;

end; % MaxMin1

• Seja f (n) o no de comparacoes entre os elementosde A.

• Quanto vale f (n) para o melhor caso, o pior casoe o caso medio?

• E possıvel melhorar esta implementacao?




• Versao 2:procedure MaxMin2(var A: Vetor; var Max,

Min: integer);

var i: integer;

begin

Max := A[1];

Min := A[1];

for i := 2 to n do

begin

if A[i] > Max then Max := A[i]

else if A[i] < Min then Min := A[i];

end;

end; % MaxMin2

• Para esta versao, temos:

– melhor caso: f (n) = n− 1 (dados em ordemcrescente)

– pior caso: f (n) = 2(n− 1) (dados em ordemdecrescente)

– caso medio: 3n2 −

32



• Calculo do caso medio:

Considerando A[i] > Max a metade das vezes,

f (n) = n− 1 +n− 1

2=

3n

2− 3

2

• E possıvel melhorar esta versao ainda mais?

• Algoritmo:

1. Compare os elementos de A aos pares (dn/2ecomparacoes).

2. Obtenha o maximo do subconjunto dosmaiores elementos (dn/2− 1e comparacoes).

3. Obtenha o mınimo do subconjunto dosmenores elementos (dn/2− 1e comparacoes).

• A notacao dxe e chamada de teto de x e retorna omenor inteiro superior a x.

• Da mesma forma, o operador piso de x, bxc,retorna o maior inteiro inferior a x.




• Versao 3:procedure MaxMin3(var A:Vetor;var Max,Min:integer);

var i, Fim: integer;

begin

if (n mod 2) > 0 then

begin

A[n+1] := A[n]; % A[n+1] e sentinela para

% vetor de tamanho ımpar

Fim := n; % Fim determina ate onde comparar

end

else Fim := n-1;

if A[1] > A[2] % Determina Max e Min iniciais

then begin Max := A[1]; Min := A[2]; end;

else begin Max := A[2]; Min := A[1]; end;

i:= 3;

while i ≤ Fim do % O laco n~ao trata casos

% especiais

begin

if A[i] > A[i+1] then

begin

if A[i] > Max then Max := A[i];

if A[i+1] < Min then Min := A[i+1];

end

else begin

if A[i] < Min then Min := A[i];

if A[i+1] > Max then Max := A[i+1];

end;

i := i+2;

end; %while

end; %MaxMin3



Versao 3 - Analise de Complexidade

• Para esta versao, o custo nos tres casos e:

f (n) =n

2+n− 2

2+n− 2

2=

3n

2− 2, para n > 0.

Comparacao da Complexidadedos 3 Algoritmos

Os tres f (n)algoritmos Melhor caso Pior caso Caso medio

MaxMin1 2(n− 1) 2(n− 1) 2(n− 1)MaxMin2 n− 1 2(n− 1) 3n/2− 3/2MaxMin3 3n/2− 2 3n/2− 2 3n/2− 2

E possıvel aumentar ainda mais a eficiencia do 3o

algoritmo?




• Versao 4 (Recursiva):procedure MaxMin4(Linf, Lsup: integer;

var Max,Min: integer);

var Max1, Max2, Min1, Min2, Meio: integer;

begin

if Lsup - Linf ≤ 1 then

if A[Linf] < A[Lsup]

then begin Max := A[Lsup];

Min := A[Linf];

end;

else begin Max := A[Linf];

Min := A[Lsup];

end

else begin

Meio := (Linf + Lsup) div 2;

MaxMin4(Linf, Meio, Max1, Min1);

MaxMin4(Meio+1, Lsup, Max2, Min2);

if Max1 > Max2 then Max := Max1

else Max := Max2;

if Min1 < Min2 then Min := Min1

else Min := Min2;

end;

end; % MaxMin4

• 1 ≤ Linf ≤ Lsup ≤ n.



Versao 4 - Analise de Complexidade

• Seja f (n) a funcao de complexidade em no decomparacoes entre os elementos de A, se Acontiver n elementos:

f (n) =

1 para n ≤ 2,f (bn/2c) + f (dn/2e) + 2 para n > 2.

• Solucao da equacao de recorrencia:quando n = 2i, i > 0, entao

f (n) = 2f (n/2) + 22f (n/2) = 4f (n/4) + 2× 24f (n/4) = 8f (n/8) + 23

... ...2i−2f (n/2i−2) = 2i−1f (n/2i−1) + 2i−1

• Apos as substituicoes, obtemos:

f (n) = 2i−1f (n/2i−1) +∑

1≤k≤i−12k

= 2i−1f (2) + 2i − 2= 2i−1 + 2i − 2= 3n/2− 2

para o melhor caso, o pior caso e o caso medio.


Documents

Aula 2