Complexidade:
Dado um problema e um algoritmo de solução queremos saber quantas operações elementares são necessárias para aplicar o algoritmo a uma instancia do problema de tamanho n, c(n).
As operações elementares que contamos são uma proxi para o tempo de execução do algoritmo e, dependendo da conveniência, podem ser por exemplo: Operações aritméticas, operações de leitura ou escrita de dados, operações de acesso a dados na memória, etc.
Problema 1: computar xn, x em R , n em N.
Apresentaremos 2 algoritmos básicos, o óbvio e o divida-e-conquiste,
cada qual em uma versão recursiva e uma versão iterativa.
Na versao recursiva a funcao chama a si mesma, com um argumento (x,m) , m<n.
No algoritmo óbvio, m = n - 1, enquanto no divida-e-conquiste m = floor(n/2).
Na versão iterativa os cálculos efetuados são praticamente os
mesmos, mas não usamos o recurso de chamar a função recursivamente.
function z = power1(x,n)
%*** versao recursiva ***
%*** do algoritmo obvio ***
if ( n == 0 )
z = 1;
else
z = x*power1(x,n-1);
end
%**************************
function z = power2(x,n)
%*** versao iterativa ***
%*** do algoritmo obvio ***
if ( n == 0 )
z = 1;
else
z = 1;
k = n;
while ( k >= 1 )
z = x*z;
k = k-1;
end %while
end %if
%**************************
function z = power3(x,n)
%*** versao recursiva do algoritmo ***
%*** estrategia divida e conquiste ***
if (n == 0)
z = 1;
else
q = floor( n/2 ); %quociente
r = n - 2*q; %resto = n mod 2
y = power3(x,q);
z = y*y;
if ( r == 1 ) %n impar
z = x*z;
end
end
%************************************
function z = power4(x,n)
%*** versao iterativa do algoritmo ***
%*** estrategia divida e conquiste ***
k=n;
z=1;
y=x;
while ( k > 0 )
q = floor( k/2 ); %quociente
r = k - 2*q; %resto = k mod 2
if ( r == 1 ) %k impar
z=y*z;
end %if
y=y*y;
k=q;
end %while
%*************************************
Tomando o produto como Operação Elementar, é fácil verificar que o número de OE's executadas em cada algoritmo é:
C1(n) = C2(n) = n e
C3(n) = C4(n) <= 2*log2(n)
Muitas vezes estamos interessados apenas em saber um limite superior para a complexidade de uma algoritmo, expresso em uma forma simples.
Se, dada uma funcao f(n) , existem constantes K e N | n >= N => f(n) <= K*g(n), então dizemos que "f é da ordem de g" , ou f=O(g).
Assim, dizemos que a complexidade dos dois primeiros algoritmos é da ordem de n, enquanto a complexidade dos dois ultimos é da ordem de log2(n) .