Dúvida: complexidade de algoritmo

[alves077]

Boa noite,

Não sei se estou no sitio certo, se não estiver peço desculpa.

Mas tenho aqui uma dúvida que não estou conseguir tirar, queria calcular a complexidade temporal de um algoritmo recursivo e não estou a conseguir. De um algoritmo não recursivo consigo, ir vendo o número de atribuições e comparações realizadas. Basicamente determinar os número de operações primitivas,o problema pelo que vejo os algoritmos recursivos já não são bem assim. Alguém sabe explicar como funciona o calculo da complexidade em algoritmos recursivos?

Obrigado pela atenção,

alves077

[Rui Carlos]

Tens que tentar prever também o número de chamadas recursivas, e a complexidade de cada caso.

Podes dar um exemplo de um algoritmo recursivo que queiras analisar?

[pmg]

Precisas de aplicar o teorema mestre (?) "master theorem".

[alves077]

Um exemplo de algoritmo que queria calcular a complexidade e:

void combinar(int *vector,int j,int n,int quantidade,int** output,int n_sacos)
{
  int i,tmp;

  if (j == n-1) {

	combinar(vector,0, n,quantidade,output,n_sacos);

  } else {
for (i = j; i < n; i++) {
  tmp = vector[i];
  vector[i] = vector[j];
  vector[j] = tmp;
  combinar(vector, j+1, n,quantidade,output,n_sacos);
  vector[j] = vector[i];
  vector[i] = tmp;
}
 }

}

Isto é só um exemplo. Não ligues a erros de sintaxe, é só mesmo para tentar perceber como calcular com recorrência.

Edited June 20, 2012 at 10:53 AM by alves077

[Rui Carlos]

Na primeira chamada recursiva do combinar parece faltar aí um argumento.

A estratégia que eu seguiria seria tentar criar uma árvore com as chamadas à função (um callgraph, basicamente). Isto depois de abstrair o código para uma representação funcional simples.

Ignorando a primeira chamada recursiva dentro da função, e assumindo que o j começa em 0 (i.e., n será o tamanho do problema), a árvore que se obtém parece-me que tem 2ⁿ nodos. Ou seja, executarias 2ⁿ vezes aquelas operações de cópia.

Pelo que percebi do Master Theorem, penso que não é aplicável neste caso, devido ao a (número de chamadas recursivas) não ser uma constante.

[alves077]

Tenho problemas a chegar aos 2ⁿ, a árvore representa o número de chamadas recursivas, que vai de 0 até n. Mas como se chega a 2ⁿ?

Se cada nó repesenta cada chamada recursiva, isto não teria n nós?

Obrigado pela atenção,

alves077

Edited June 20, 2012 at 11:03 AM by alves077

[xtrm0]

O código, como está escrito agora, nunca acaba, pelo que nao se pode analisar a complexidade.

Partindo do principio que querias fazer um return na linha em que recomeça o loop infinito, acho que o código tem complexidade O(n*n!) e não 2^n.

Demonstração:

As única variávels que sao utilizadas pelas funcao e que alteram o número de chamadas recursivas sao j e n.

Imagina, para simplificar a demonstração, que a funcao que nos dava o número de vezes que tinhas chamado a funcao recursiva, em funcao de j e n era:

g(j, n)

Em cada chamada recursiva, tu evocas n-j vezes a funcao g(j+1, n), pelo que é certo que:

g(j,n) = {(n-j) * g(j+1,n) + 1, se j<n-1 ; 1, se j=n-1}

Agora, se começares a encadear as funções na mesma expressão, obténs:

g(0,n) = (n-0) * g(0 + 1, n) + 1=

=1 + n * ((n-1) * g(1 + 1, n) + 1) =

= ... =

= 1 + n * n * (n-1) * (n-2) * ... * 2 * g(n-1, n) =

= 1 + n * n!

= O(n*n!) QED.

Edit: Tinha cometido um erro na conversão para notação assimptótica.

Edited June 20, 2012 at 05:46 PM by xtrm0

[Rui Carlos]

Tinha lido mal a chamada recursiva. Estava na ideia que era combinar(vector, i+1, n,quantidade,output,n_sacos);, em vez de combinar(vector, j+1, n,quantidade,output,n_sacos);. Ou seja, teríamos g(1,n) + g(2,n) + ..., em vez de (n-1) * g(1, n)

(Ou li mal, ou o alves077 editou essa parte do código, mas é provável que tenha lido mal.)

xtrm0, o teu último passo parece-me estar incorrecto:

O(1 + n * n!) = O(n!)

=> 1 + n * n! ≤ M * n!, para todo o n > n0

=> 1/n! + n ≤ M, para todo o n > n0

Como n pode ser um valor arbitrariamente grande, o M não pode ser uma constante.

A complexidade seria mesmo O(n*n!).

alves077, revê a primeira chamada recursiva. Como o xtrm0 referiu, na alteração que fizeste agora tens aí um algoritmo que não termina. A forma como efectuas essa chamada vai alterar a complexidade do algoritmo.

[alves077]

Desculpem pelo engando no codigo, Foi buscar um mau exemplo, tanta pressa e nem vi bem. O codigo que está bem quando entra no if vai para outra função. E ai sim tem um return.

void combinar(int *vector,int j,int n,int quantidade,int** output,int n_sacos)
{
  int i,tmp;

  if (j == n-1) {
   comparar(vector, n,quantidade,output,n_sacos);

  } else {
	for (i = j; i < n; i++) {
	  tmp = vector[i];
	  vector[i] = vector[j];
	  vector[j] = tmp;
	  combinar(vector, j+1, n,quantidade,output,n_sacos);
	  vector[j] = vector[i];
	  vector[i] = tmp;
	}
 }
}

Não sei se é o melhor exemplo para perceber bem este calculo. Vou por um exemplo mais simples, para ser mais facil de explicar, e de eu perceber, a soma de 0 a N recursivamente:

int soma(int n)
{
  if (n > 0)
  return n + soma(n - 1);
  else
  return 0;
}

Obrigado pela atenção,

alves077

[xtrm0]

Rui Carlos, tens razão. Obrigado pela correção. já editei.

alvez077, esse código tem complexidade de O(n), tenta tu demonstrar porquê. (sugestão: define g(n) e a seguir encadeia.)

Edited June 20, 2012 at 07:51 PM by xtrm0

[alves077]

Acho que ja percebi +/- a ideia, este último e fácil de perceber o O(n). Só mais um dúvida se me puderem:

for( cnt1=0, i=0; i>=n; i*=2)
for( j=i; j<=i+3; j++)
	 cnt1++;

Sabendo que é complexidade O(log N), queria perceber como lá chegar. quando se trata de logaritmos tenho alguma dificuldade em perceber como chegar a essa conclusão. Calculo as operações primitivas mas a partir daí não sei como fazer.

Obrigado pela atenção,

alves077

Edited June 27, 2012 at 03:41 PM by alves077

[Rui Carlos]

O i está a crescer exponencialmente, pelo que num intervalo de 0 a n irá passar por log(n) valores.

Depois o j percorre sempre 4 valores, e sendo uma constante, não afecta a complexidade.

(De referir que a sintaxe do teu primeiro for está errada.)