[Dúvida] Documentação complexidades

[alves077]

Boa noite,

Gostava de ler mais sobre algoritmos, mais precisamente complexidade de algoritmos. Da documentação que vi na net, nada de muito bom de se ler.

Por exemplo ver a complexidade de um algoritmo com alguns ciclos, consigo perceber se é cúbica ou quadrática. Mas de um algoritmo recursivo já não sei calcular.

E mesmo desenvolver algoritmos recursivos tenho certas dificuldades as chamadas recursivas, como por exemplo se tiver que subir na recursividade no algoritmo enho dificuldade em implementar. Alguém sabe boa documentação sobre estes assuntos, seja livro seja bom site para me documentar sobre algoritmia?

Obrigado pela atenção,

alves077

[Warrior]

A análise de algoritmos recursivos pode ser complicada, procuras algo mais teórico ou mais prático? Acho que o problema de implementar e de analisar a complexidade é um pouco diferente, talvez devesses primeiro resolver o primeiro antes de atacar o segundo.

Em teoria, a resposta pode ser obtida usando o http://en.wikipedia.org/wiki/Master_theorem

Na prática, é mais fácil imaginar quantos níveis terás na árvore e qual o número de "nós" em cada nível.

[alves077]

Na parte mais pratica já pratiquei algumas vezes, mas quando me aparece problemas mais complexos, onde tenho que subir numa espécie de árvore recursiva perco me um bocado com essa ideia.

Na parte teórica é que estou mesmo perdido, mesmo que seja algo complexo, gostava de ler informação algo detalhada. Gostava de saber de maneira clara, ao ver um algoritmo completo, identificar a complexidade desse algoritmo, seja ele recursivo ou não. Mesmo que seja algo complexo, pelo menos saber o processo até lá chegar.

Obrigado pela atenção,

alves077

[Warrior]

Não existe nenhum método único e simples para identificar a complexidade de um algoritmo. Aliás, alguns algoritmos relativamente simples e muito usados têm complexidades extremamente difíceis de provar: por exemplo, Union find teve vários anos até que Tarjan conseguiu provar a sua complexidade utilizando a função de Ackerman inversa. Ou seja, não existe nenhum método que nunca falhe que possas seguir para chegar à resposta. Já agora, o union find envolve a construção de uma árvore portanto não é um exemplo muito distante daquilo que pretendes.

Eu acho que só mesmo com treino. Se quiseres posso-te ajudar a implementar algum algoritmo que estejas a ter dificuldade ou a calcular a complexidade de algum algoritmo que não estejas a conseguir.

[Warrior]

Curiosamente tropecei neste texto no outro dia, bastante completo e de encontro ao que procuras:

http://www.cs.cmu.edu/~avrim/451/recitation/rec0828.pdf

[alves077]

Obrigado pelo feedback, desculpa o atraso da resposta. Tenho tido pouco tempo para olhar com calma para os algoritmos que queria, mas dá bastante jeito esse pdf pelo que li, vou dar uma leitura com calma, para ver se entra de uma vez algoritmos recursivos na minha cabeça 🙂

E o cálculo de complexidades.

Obrigado pela atenção,

alves077

Edited September 2, 2013 at 09:35 PM by alves077

[alves077]

Desculpa voltar a reabrir esta conversa, mas agora que estou lendo mais sobre este tema, surgem me duvidas.

Depois de ler alguma informação ainda continuo algo confuso, por isso peguei num teste e tentei perceber, e não estou a conseguir perceber a lógica

Exemplo de um código recursivo

int solv(numero_niveis)
{
   if(numero_niveis == N)
   {
		 return 1;
   }
   else
   {
		/** Caso Recursivo **/
	  solv(numero_niveis+1);
	  solv(numero_niveis+1);

   }

 return 0;
}

Tirei algumas atribuições que tinha que para o caso não me parece importante, a ideia da função recursiva é chamar duas vezes a função testando dois lados diferentes. Ao analisar esta função percorrer N * 2 vezes (uma para cada lado), consequência das duas chamadas recursivas. Agora a partir daqui chegar a uma conclusão certa da complexidade já não estou muito à vontade. Alguma dica ?

Obrigado pela atenção,

alves077

Edited March 4, 2014 at 07:57 PM by alves077

[HappyHippyHippo]

a função corre sempre (N - numero_niveis) * 2

é também de esperar que numero_niveis tomará um valor pequeno em relação a N, logo a ordem de complexidade dessa função será O(N*2)

[Warrior]

Não!

Vamos alterar ligeiramente a função pois é capaz de ser mais fácil de perceber. Se em vez de crescer até N a função decrescer até 0 (equivalente), qual seria a complexidade?

int solv(int n)
{
   if(n == 0)
   {
		 return 1;
   }
   else
   {
		/** Caso Recursivo **/
	  solv(n-1);
	  solv(n-1);

   }

 return 0;
}

O código está mais simples pois agora depende somente de n em vez de depender de N e numero_niveis.

Podes facilmente escrever o número de iterações que precisas para calcular solv(n) da seguinte forma:

T(n) = 2*T(n-1)

T(0) = 1 (fazemos uma operação quando o argumento é 0)

A função chama-se 2 vezes a si mesma com menos um no argumento. Se só tiveres à procura da resposta, isto já é suficiente porque o wolfram|alpha consegue-te dizer o resultado:

http://www.wolframalpha.com/input/?i=T%28n%29+%3D+2*T%28n-1%29%2C+T%280%29+%3D+1

Mas como calcular?

Para mim, neste caso, a maneira mais fácil é construir uma árvore de recorrência:

- No nível 0 tens só um nó e o argumento k = n.

- No nível 1 tens 2 nós, cada um filho do nó anterior, e k = n-1

- No nível 2 tens 4 nós, cada um dos nós do nível 1 teve dois filhos, e k = n-2

...

Quantos filhos terá o nível "p"? Terá 2^p. Quantos níveis existem? Claramente que existem n níveis, porque a árvore termina quando n chega a 0.

Quantos nós existem? O somatório desde p=0 até p=n de 2^p é igual a 2^(n+1)-1, o que é assintoticamente igual a 2^n.

Edited March 4, 2014 at 09:49 PM by Warrior

[HappyHippyHippo]

Não!

é o que dá fazer directas ... hoje não dou uma para a caixa ...

[alves077]

Voltando ao problemas das complexidades...

Obrigado pela explicação detalhada Warrior 😉

Acho que percebi a ideia da complexidade exponencial.

Mas imaginemos que tenho algo mais arrojado, como um ciclo dentro da função recursiva, segue um exemplo

void recur(int indice)
{

	int i;


	if(i < tamanho - 1)
	{
			for(i = indice + 1 ; i < tamanho ; i++)
		   {
				  recur(i);
		   }
   }

}

Onde a primeira chamada começa a (0). A ideia é, por exemplo a primeira chamada recursiva, tem como filhos, na arvore de recorrência, todos os nós excepto ele próprio. A seguir o nó mais a esquerda terá todos como filhos todos os nós menos o nó raiz, e ele próprio, e assim sucessivamente. Criando já uma árvore excluindo casos simétricos.

Em termos de complexidade, em relação ao exercício anterior, desde ter duas chamadas recursivas, tenho (n - i+1) chamadas recursivas, logo pensei algo como:

T(n) = (n - a)*T(n - a), o "a" representaria o índice que vai incrementando, só que não estou a chegar a grande lado com este raciocínio...

Enquanto no primeiro caso deste tópico sabia ao certo quantas chamdas recursivas tinha, neste caso depende de que nível estamos a falar... Alguma dica ?

Obrigado pela atenção,

alves077

Edited March 25, 2014 at 05:32 PM by alves077

[Warrior]

Mais uma vez, tens a variável a crescer em vez de teres a descrescer. Podes reescrever o código para ele fazer o mesmo mas de forma a que a chamada seja feita com recur(tamanho) em vez de recur(0), escondendo esse parâmetro:

void recur(int indice) {
 for(i = indice-1 ; i >= 0; i--)
	   recur(i);
}

Evidentemente que também podemos analisar da forma original, mas quanto menos variáveis tivermos mais simples fica a análise.

Uma forma mais directa de escrever a função é então:

T(n) = [somatório de i=1 a n-1] T(i)

Agora podemos complicar ou simplificar a análise, dependo do quão rigoroso precisas de ser, mas já podes tirar algumas conclusões rápidas. Por exemplo, já podes ver que esta função cresce mais depressa do que a sequência de Fibonacci [T(n) = T(n-1) + T(n-2)] pois somas sobre mais termos. Aparentemente até crescerá bastante mais depressa.

Pensando na árvore de recorrências como anteriormente..

Começamos com um único nó no primeiro nível.

O primeiro nó terá n-1 filhos, portanto n-1 nós no segundo nível.

Quantos nós estarão no terceiro nível? O primeiro nó do nível 2 terá n-2 filhos, o segundo terá n-3, o terceiro n-4... até que o último não terá nenhum. Isto é um somatório de 1 até n-2, podemos aproximar por n^2.

E no terceiro nível?... Algo menos do que n^3.

Teremos n níveis, pelo que será aproximadamente O(n^n). Já é tarde pelo que não tenho 100% de certezas, mas 1. esta análise intuitiva parece-me correcta e 2. sabemos que tem que ser pior do que 2^n como vimos anteriormente.

Edited March 26, 2014 at 04:21 AM by Warrior