Jump to content
Sign in to follow this  
alves077

[Dúvida] Documentação complexidades

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Edited by Rui Carlos
Corrigido link.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
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)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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 by Warrior
  • Vote 1

Share this post


Link to post
Share on other sites
HappyHippyHippo

Não!

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


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

Share this post


Link to post
Share on other sites
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 by Warrior

Share this post


Link to post
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
Sign in to follow this  

×
×
  • 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.