Jump to content

Dúvida: complexidade de algoritmo


alves077
 Share

Recommended Posts

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

Link to comment
Share on other sites

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 by alves077
Link to comment
Share on other sites

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 2n nodos. Ou seja, executarias 2n 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.

Link to comment
Share on other sites

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

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

Obrigado pela atenção,

alves077

Edited by alves077
Link to comment
Share on other sites

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 by xtrm0

<Signature goes here>

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 by xtrm0

<Signature goes here>

Link to comment
Share on other sites

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 by alves077
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.