COMPARAÇÃO MÉTODOS
DIRETOS E ITERATIVOS
MEDIDA DO TEMPO DE
EXECUÇÃO DE UM PROGRAMA
O projeto de algoritmos é fortemente influenciado
pelo estudo de seus comportamentos.
 Depois que um problema é analisado e decisões
de projeto são finalizadas, é necessário estudar as
várias opções de algoritmos a serem utilizados,
considerando os aspectos de tempo de execução e
espaço ocupado.
 Muitos desses algoritmos são encontrados em
áreas como pesquisa operacional, otimização,
teoria dos grafos, estatística, probabilidades,
entre outras.

CUSTO DE UM ALGORITMO
Determinando o menor custo possível para
resolver problemas de uma dada classe, temos a
medida da dificuldade inerente para resolver o
problema.
 Quando o custo de um algoritmo é igual ao menor
custo possível, o algoritmo é ótimo para a medida
de custo considerada.
 Podem existir vários algoritmos para resolver o
mesmo problema.
 Se a mesma medida de custo é aplicada a
diferentes algoritmos, então é possível comparálos e escolher o mais adequado.

FUNÇÃO DE COMPLEXIDADE




A complexidade computacional de um algoritmo se
refere à estimativa do esforço computacional
despendido para resolver o problema e é medido pelo
número necessário de operações aritméticas e lógicas.
(Ex.: número de Adições e Multiplicações para
resolver um sistema linear).
Para medir o custo de execução de um algoritmo é
comum definir uma função de custo ou função de
complexidade f.
f(n) é a medida do tempo necessário para executar um
algoritmo para um problema de tamanho n.
A complexidade de tempo na realidade não representa
tempo diretamente, mas o número de vezes que
determinada operação considerada relevante é
executada.
EXEMPLO - MAIOR ELEMENTO

Considere o algoritmo para encontrar o maior elemento de
um vetor de inteiros A[1::n]; n 1.
function Max (var A: Vetor ) : integer ;
var i , Temp: integer ;
begin
Temp := A[1] ;
for i := 2 to n do i f Temp < A[ i ] then Temp := A[ i ] ;
Max := Temp;
end;



Seja f uma função de complexidade tal que f(n) é o número
de comparações entre os elementos de A, se A contiver n
elementos.
Logo f(n) = n - 1; para n > 0.
Qualquer algoritmo para encontrar o maior elemento de
um conjunto com n elementos, n ≥ 1, faz pelo menos n - 1
comparações.
TAMANHO DA ENTRADA DE DADOS
A medida do custo de execução de um algoritmo
depende principalmente do tamanho da entrada
dos dados.
 É comum considerar o tempo de execução de um
programa como uma função do tamanho da
entrada.

ELIMINAÇÃO DE GAUSS

Algoritmo:
function [x] = gauss(n, A, b)
c = [A b];
for ( j = 1:(n - 1) )
r = 1 / c(j,j);
for ( i = (j + 1):n )
Mult = c(i,j) * r;
c(i,j) = c(i,j) - Mult * c(j,j);
for ( k = (j + 1):(n + 1) )
c(i,k) = c(i,k) - Mult * c(j,k);
endfor
endfor
endfor
x = zeros(n,1);
x(n) = c(n,(n+1)) / c(n,n);
for ( i = (n - 1):-1:1 )
Soma = 0;
for ( j = (i + 1):n )
Soma = Soma + c(i,j) * x(j);
endfor
x(i) = ( c(i,(n+1)) - Soma ) / c(i,i);
endfor
endfunction
ELIMINAÇÃO DE GAUSS

Principal parte:
for ( j = 1:(n - 1) )
...
for ( i = (j + 1):n )
...
for ( k = (j + 1):(n + 1) )
...
endfor
endfor
endfor
Complexidade O(n3)
 Métodos Diretos = O(n3)

JACOBI

Algoritmo:
function [x] = jacobi(n, A, b, Toler, IterMax)
for ( i = 1:n )
r = 1 / A(i,i);
for ( j = 1:n )
if ( i ~= j ) A(i,j) = A(i,j) * r; endif
endfor
b(i) = b(i) * r; x(i) = b(i);
endfor
Iter = 0;
while (1)
Iter = Iter + 1;
for ( i = 1:n )
Soma = 0;
for ( j = 1:n )
if ( i ~= j ) Soma = Soma + A(i,j) * x(j); endif
endfor
v(i) = b(i) - Soma;
endfor
NormaNum = 0; NormaDen = 0;
for ( i = 1:n )
t = abs( v(i) - x(i) );
if ( t > NormaNum ) NormaNum = t; endif
if ( abs(v(i)) > NormaDen ) NormaDen = abs(v(i)); endif
x(i) = v(i);
endfor
NormaRel = NormaNum / NormaDen;
if ( (NormaRel <= Toler) | (Iter >= IterMax) ) break; endif
endwhile
if ( NormaRel <= Toler ) CondErro = 0;
else CondErro = 1; endif
endfunction
JACOBI

Principal parte:
while (1)
...
for ( i = 1:n )
...
for ( j = 1:n )
...
endfor
endfor
...
for ( i = 1:n )
...
endfor
...
if ( (NormaRel <= Toler) | (Iter >= IterMax) ) break; endif
endwhile


Complexidade 2kn2 + n2 + n + 2k = O(n2)
Métodos Iterativos = O(n2)
EXECUÇÃO
A = 10x10, 20x20, 30x30, ..., 200x200
 n = 10, 20, 30, ..., 100.


Método Direto - Eliminação de Gauss

Método Iterativo - Jacobi
Toler = 10-7
 IterMax = 50

COMPARAÇÃO ENTRE
ELIMINAÇÃO DE GAUSS E JACOBI
100
Tempo (s)
80
60
Eliminação Gauss
Jacobi
40
20
0
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
n
DÚVIDAS?